摘要翻译：
可以使用自动机或形式语言紧凑地指定范围广泛的约束。在最近的一系列论文中，我们已经表明，用这种规范进行推理的有效方法是将它们分解为本原约束。例如，我们可以使用最先进的SAT求解器，并从它们的高级功能中获益，如快速单元传播、子句学习和基于冲突的搜索启发式。这种方法为解决调度、排班和配置中的组合问题以及生物信息学、软件测试和自然语言处理等更多领域的问题提供了希望。此外，分解可能是传播其他全局约束的有效方法。
---
英文标题：
《Decompositions of Grammar Constraints》
---
作者：
Claude-Guy Quimper and 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中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Formal Languages and Automata Theory        形式语言与自动机理论
分类描述：Covers automata theory, formal language theory, grammars, and combinatorics on words. This roughly corresponds to ACM Subject Classes F.1.1, and F.4.3. Papers dealing with computational complexity should go to cs.CC; papers dealing with logic should go to cs.LO.
涵盖自动机理论，形式语言理论，文法，和词的组合学。这大致相当于ACM主题类F.1.1和F.4.3。处理计算复杂性的论文应该上CS.CC；处理逻辑的论文应该去CS.LO。
--

---
英文摘要：
  A wide range of constraints can be compactly specified using automata or formal languages. In a sequence of recent papers, we have shown that an effective means to reason with such specifications is to decompose them into primitive constraints. We can then, for instance, use state of the art SAT solvers and profit from their advanced features like fast unit propagation, clause learning, and conflict-based search heuristics. This approach holds promise for solving combinatorial problems in scheduling, rostering, and configuration, as well as problems in more diverse areas like bioinformatics, software testing and natural language processing. In addition, decomposition may be an effective method to propagate other global constraints.
---
PDF链接：
https://arxiv.org/pdf/0903.0470