On the computational complexity of satisfiability in propositional logics of programs

DOI10.1016/0304-3975(89)90083-2zbMath0496.68020OpenAlexW2047769025MaRDI QIDQ1170028

Bogdan S. Chlebus

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90083-2

zbMATH Keywords

satisfiability problemnondeterminismcomplexity classespropositional dynamic logicpropositional algorithmic logicalternating Turing machine

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Other nonclassical logic (03B60) Abstract data types; algebraic specification (68Q65) Complexity of computation (including implicit computational complexity) (03D15) General topics in the theory of software (68N01)

Related Items (1)

Domino-tiling games

Cites Work

• A near-optimal method for reasoning about action
• Space-bounded reducibility among combinatorial problems
• Propositional dynamic logic of regular programs
• Relationships between nondeterministic and deterministic tape complexities
• Decision complexity of variants of propositional dynamic logic
• Alternation
• Completeness Proofs for Some Logics of Programs
• On the Decidability of Propositional Algorithmic Logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the computational complexity of satisfiability in propositional logics of programs