摘要翻译：
许多问题可以由依赖于参数的命题公式的模式来指定，例如电路的规格通常依赖于其输入的位数。我们定义了一个逻辑，它的公式称为“迭代模式”，允许表达这样的模式。图式用索引命题，例如P_i、P_i+1、P_1和广义联结词，例如/\i=1..n或i=1..n（称为“迭代”）来扩展命题逻辑，其中n是一个（未绑定的）整数变量，称为“参数”。迭代图式的表达能力严格地大于命题逻辑：它甚至超出了一阶逻辑的范围。我们定义了一个证明过程，称为DPLL*，它可以证明一个模式对其参数的至少一个值是可满足的，这是基于DPLL过程的精神。然而，相反的问题，即证明一个模式对于参数的每个值都是不可满足的，是不可判定的，因此DPLL*通常不会终止。然而，我们证明它终止于一个称为“规则嵌套”的句法子类的图式。这是DPLL*被证明终止的第一个非平凡类。此外，规则嵌套模式类是第一个允许迭代嵌套的可判定类，即允许形式为/\i=1..n(/\j=1..n...)的模式。
---
英文标题：
《A Decidable Class of Nested Iterated Schemata (extended version)》
---
作者：
Vincent Aravantinos, Ricardo Caferra, Nicolas Peltier
---
最新提交年份：
2010
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Logic in Computer Science        计算机科学中的逻辑
分类描述：Covers all aspects of logic in computer science, including finite model theory, logics of programs, modal logic, and program verification. Programming language semantics should have Programming Languages as the primary subject area. Roughly includes material in ACM Subject Classes D.2.4, F.3.1, F.4.0, F.4.1, and F.4.2; some material in F.4.3 (formal languages) may also be appropriate here, although Computational Complexity is typically the more appropriate subject area.
涵盖计算机科学中逻辑的所有方面，包括有限模型理论，程序逻辑，模态逻辑和程序验证。程序设计语言语义学应该把程序设计语言作为主要的学科领域。大致包括ACM学科类D.2.4、F.3.1、F.4.0、F.4.1和F.4.2中的材料；F.4.3（形式语言）中的一些材料在这里也可能是合适的，尽管计算复杂性通常是更合适的主题领域。
--
一级分类：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中的材料。
--

---
英文摘要：
  Many problems can be specified by patterns of propositional formulae depending on a parameter, e.g. the specification of a circuit usually depends on the number of bits of its input. We define a logic whose formulae, called "iterated schemata", allow to express such patterns. Schemata extend propositional logic with indexed propositions, e.g. P_i, P_i+1, P_1, and with generalized connectives, e.g. /\i=1..n or i=1..n (called "iterations") where n is an (unbound) integer variable called a "parameter". The expressive power of iterated schemata is strictly greater than propositional logic: it is even out of the scope of first-order logic. We define a proof procedure, called DPLL*, that can prove that a schema is satisfiable for at least one value of its parameter, in the spirit of the DPLL procedure. However the converse problem, i.e. proving that a schema is unsatisfiable for every value of the parameter, is undecidable so DPLL* does not terminate in general. Still, we prove that it terminates for schemata of a syntactic subclass called "regularly nested". This is the first non trivial class for which DPLL* is proved to terminate. Furthermore the class of regularly nested schemata is the first decidable class to allow nesting of iterations, i.e. to allow schemata of the form /\i=1..n (/\j=1..n ...).
---
PDF链接：
https://arxiv.org/pdf/1001.4251