COMPLEXITY RESULTS FOR CLASSES OF QUANTIFICATIONAL FORMULAS
COMPLEXITY RESULTS FOR CLASSES OF QUANTIFICATIONAL FORMULAS
复制标题
DOI：
10.1016/0022-0000(80)90027-6
复制
发表时间：
1980-01-01
影响因子：
1.1
通讯作者：
LEWIS, HR
中科院分区：
文献类型：
--
作者：
LEWIS, HR
我们分析了当F是经典谓词演算中满足一定句法约束的公式时，判定F是否可满足的计算复杂性。例如，对于一元谓词演算和Gödel or 3…∃∀∀∃…3前缀类，得到了形式cn/logn的不确定性时间下界和上界。通过使用时间受限图灵机的接受问题和交替的下推和堆叠自动机来建立下界。
We analyze the computational complexity of determining whetherFis satisfiable whenFis a formula of the classical predicate calculus obeying certain syntactic restrictions. For example, for the monadic predicate calculus and the Gödel or 3 … ∃∀∀∃ … 3 prefix class we obtain lower and upper nondeterministic time bounds of the formcn/logn. The lower bounds are established by using acceptance problems for time-bounded Turing machines and alternating pushdown and stack automata.