Tarskian set constraints

DOI10.1006/inco.2001.2973zbMath1009.03019MaRDI QIDQ1854523

Dexter Kozen, David Allen McAllester, Robert L. Givan, Carl Witty

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.2973

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B70: Logic in computer science

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

Related Items

Automated theorem proving by resolution in non-classical logics, Decision Procedures for Region Logic, Generalized Satisfiability for the Description Logic $\mathcal{ALC}$

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Attributive concept descriptions with complements
• Results on the propositional \(\mu\)-calculus
• An automata theoretic decision procedure for the propositional mu- calculus
• A near-optimal method for reasoning about action
• Complexity results for classes of quantificational formulas
• Natural language syntax and first-order inference
• Propositional dynamic logic of regular programs
• Efficient inference of partial types
• Decidability of systems of set constraints with negative constraints
• Varieties of complex algebras
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Taxonomic syntax for first order inference
• Boolean Algebras with Operators. Part I
• Boolean Algebras with Operators