摘要翻译：
通过形式语言来指定在名册和其他领域中的全局约束是一种很有吸引力的机制。例如，规则约束和语法约束分别根据自动机和上下文无关语法接受的语言指定约束。利用约束的固定长度，我们给出了一个将上下文无关文法转换为自动机的算法。然后，我们研究了最小化技术的使用，以减少这种自动机的大小，并加快传播速度。我们证明了这样的自动机在展开后最小化和最初缩小的域可以得到比在展开和缩小前最小化更紧凑的自动机。实验结果表明，这样的转换可以改善我们可以“建模和运行”的罗列问题的规模。
---
英文标题：
《Reformulating Global Grammar Constraints》
---
作者：
George Katsirelos, Nina Narodytska, Toby Walsh
---
最新提交年份：
2009
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  An attractive mechanism to specify global constraints in rostering and other domains is via formal languages. For instance, the Regular and Grammar constraints specify constraints in terms of the languages accepted by an automaton and a context-free grammar respectively. Taking advantage of the fixed length of the constraint, we give an algorithm to transform a context-free grammar into an automaton. We then study the use of minimization techniques to reduce the size of such automata and speed up propagation. We show that minimizing such automata after they have been unfolded and domains initially reduced can give automata that are more compact than minimizing before unfolding and reducing. Experimental results show that such transformations can improve the size of rostering problems that we can 'model and run'.
---
PDF链接：
https://arxiv.org/pdf/0903.0475