On the computational complexity of satisfiability in propositional logics of programs

DOI10.1016/0304-3975(89)90083-2MaRDI QIDQ1170028zbMATH OpenOpenAlexFDO

Authors 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

alternating Turing machinecomplexity classesnondeterminismpropositional algorithmic logicpropositional dynamic logicsatisfiability problem

Mathematics Subject Classification ID

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

Cites work

• A near-optimal method for reasoning about action
• Alternation
• Completeness Proofs for Some Logics of Programs
• Decision complexity of variants of propositional dynamic logic
• scientific article; zbMATH DE number 3461480 (Why is no real title available?)
• scientific article; zbMATH DE number 3597842 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3315203 (Why is no real title available?)
• On the Decidability of Propositional Algorithmic Logic
• Propositional dynamic logic of regular programs
• Relationships between nondeterministic and deterministic tape complexities
• Space-bounded reducibility among combinatorial problems

Cited in

(1)

• Domino-tiling games

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1170028)