Large Language Models (LLMs) excel at generating fluent text but struggle to enforce external constraints because they generate tokens sequentially without explicit control mechanisms. GenCP addresses this limitation by combining LLM predictions with Constraint Programming (CP) reasoning, formulating text generation as a Constraint Satisfaction Problem (CSP). In this paper, we improve GenCP by integrating Masked Language Models (MLMs) for domain generation, which allows bidirectional constraint propagation that leverages both past and future tokens. This integration bridges the gap between token-level prediction and structured constraint enforcement, leading to more reliable and constraint-aware text generation. Our evaluation on COLLIE benchmarks demonstrates that incorporating domain preview via MLM calls significantly improves GenCP's performance. Although this approach incurs additional MLM calls and, in some cases, increased backtracking, the overall effect is a more efficient use of LLM inferences and an enhanced ability to generate feasible and meaningful solutions, particularly in tasks with strict content constraints.

Constraint Programming (CP) and Machine Learning (ML) face challenges in text generation due to CP's struggle with implementing "meaning'' and ML's difficulty with structural constraints. This paper proposes a solution by combining both approaches and embedding a Large Language Model (LLM) in CP. The LLM handles word generation and meaning, while CP manages structural constraints. This approach builds on GenCP, an improved version of On-the-fly Constraint Programming Search (OTFS) using LLM-generated domains. Compared to Beam Search (BS), a standard NLP method, this combined approach (GenCP with LLM) is faster and produces better results, ensuring all constraints are satisfied. This fusion of CP and ML presents new possibilities for enhancing text generation under constraints.

Around twenty years ago, Generative Constraint Programming techniques, such as the Generative Constraint Satisfaction Problem (GCSP), were developed to deal with problems mainly based on functional constraints or relaxation of such constraints, like the ones in industrial configuration problems. In 2023, we introduced On-the-fly Constraint Programming Search (OTFS), inspired by GCSP, to successfully tackle Model Checking problems that have a lot of functional constraints. This paper aims to show that a revised version of OTFS, called GenCP, can also be used on classical textbook CP problems that do not involve constraints resembling functional constraints: the NQueens and All-Interval problems, and two lesser known CP problems, Graceful Graphs and Langford Number. GenCP significantly reduces execution times on these problems, showing that it is a valid alternative to traditional CP.

Model Checking (MC) and Constraint Programming (CP) are complementary techniques with the potential for mutual improvement. In this paper, we focus on leveraging on-the-fly MC techniques to improve the performance of a CP solver for dynamic problems. To evaluate the effectiveness of our approach, we conduct a case study based on a reachability problem. Using a constructive approach inspired by MC, we propose to incorporate an on-the-fly strategy into an existing CP solver. Through comparative analysis, we evaluate this technique’s impact on the solver’s performance in terms of time and space efficiency. Our results show that the on-the-fly MC-based CP solver performs better than a pure CP solver, overcoming the limitations of the destructive approach typically used in CP. More precisely, the introduction of the on-the-fly strategy allows one to gain a factor of at least 20 in time/space. This work contributes to bridging the gap between MC and CP, highlights the potential for cross-domain improvement, and opens avenues for future research combining these powerful formal techniques.

Nowadays, the ability of providing an automated support to the management of business processes is commonly recognized as a main competitive factor for companies. One of the most critical resources to deal with is time, but, unfortunately, the time management support offered by most workflow systems is rather limited. In this paper we focus our attention on the modeling and verification of workflows extended with time constraints. We propose timed automata as an effective tool to specify timed workflow schemas and to check their consistency.