The decision problem for branching time logic

DOI10.2307/2274321MaRDI QIDQ3708772zbMATH OpenOpenAlexFDO

Authors S. Shelah, Yuri Gurevich

Publication date 1985

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2274321

zbMATH Keywords

tree automatamonadic theoryemptiness problemfirst order theorywell-founded trees

Mathematics Subject Classification ID

Trees (05C05) Modal logic (including the logic of norms) (03B45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Recommendations

• scientific article; zbMATH DE number 4006233
• The temporal logic of branching time
• Deciding full branching time logic
• scientific article; zbMATH DE number 2084388
• The decision problem for linear temporal logic

Cites work

• The monadic theory of order

Cited in

(29)

• Notes on monadic logic. Part B: Complexity of linear orders in ZFC
• Системы временной логики I: моменты, истории, деревья
• Counting on CTL^*: On the expressive power of monadic path logic
• Path logics with synchronization
• An infinite hierarchy of temporal logics over branching time
• Approximating trees as coloured linear orders and complete axiomatisations of some classes of trees
• A system of dynamic modal logic
• \(\text{BTL}_{2}\) and the expressive power of \(\text{ECTL}^{+}\)
• Pure Logic with Branched Quantifiers
• Composition over the natural number ordering with an extra binary relation
• Rules and Refutation Rules for the Logic of Finite n-ary Trees
• First-order definability of transition structures
• A finite axiomatization of the set of strongly valid Ockhamist formulas
• An improved lower bound for the elementary theories of trees
• scientific article; zbMATH DE number 2084388 (Why is no real title available?)
• A decidable temporal logic of parallelism
• Finite and Circular Path Models for Branching Time Logics
• scientific article; zbMATH DE number 4006233 (Why is no real title available?)
• Completeness of a branching-time logic with possible choices
• Interval temporal logic HS with path quantifiers
• Automata-theoretic characterisations of branching-time temporal logics
• Correspondence problems for classes of postlinear orders
• Decision procedures and expressiveness in the temporal logic of branching time
• Notes on monadic logic. A: Monadic theory of the real line
• More on monadic logic. C: Monadically interpreting in stable unsuperstable \(\mathcal T\) and the monadic theory of \(^{\omega}\lambda\)
• Arity hierarchy for temporal logics
• TABLEAUX: A general theorem prover for modal logics
• Temporal Logics with Reference Pointers and Computation Tree Logics
• Quantification over sets of possible worlds in branching-time semantics

This page was built for publication: The decision problem for branching time logic

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