Arity hierarchy for temporal logics
The paper studies the expressive power of temporal logics over trees. The main result states that in contrast to Kamp's theorem (stating, inter alia, that the temporal logic with ``Until and ``Since is expressively complete for the monadic first-order logic over the linear order of natural numbers), for every \(n\) there is a modality of arity \(n\) definable by a monadic logic formula, which is not equivalent over trees to any temporal logic formula which uses modalities of arity less than \(n\). The proof uses an instance of Shelah's composition theorem. Interesting corollaries of this result are, e.g., new proofs that CTL* and ECTL+ have no finite bases.
- \(\text{BTL}_{2}\) and the expressive power of \(\text{ECTL}^{+}\)
- An infinite hierarchy of temporal logics over branching time
- Automatic verification of finite-state concurrent systems using temporal logic specifications
- Expressive completeness of temporal logic of trees
- Fairness and related properties in transition systems - a temporal logic to deal with fairness
- scientific article; zbMATH DE number 1678388 (Why is no real title available?)
- scientific article; zbMATH DE number 3870578 (Why is no real title available?)
- scientific article; zbMATH DE number 3876574 (Why is no real title available?)
- scientific article; zbMATH DE number 4006233 (Why is no real title available?)
- scientific article; zbMATH DE number 747023 (Why is no real title available?)
- scientific article; zbMATH DE number 3714896 (Why is no real title available?)
- scientific article; zbMATH DE number 1086492 (Why is no real title available?)
- scientific article; zbMATH DE number 1142326 (Why is no real title available?)
- scientific article; zbMATH DE number 1927553 (Why is no real title available?)
- scientific article; zbMATH DE number 3290311 (Why is no real title available?)
- Monadic Logic of Order over Naturals has no Finite Base
- The decision problem for branching time logic
- The first order properties of products of algebraic systems
- The monadic theory of order
- Uniformization, choice functions and well orders in the class of trees
- “Sometimes” and “not never” revisited
- An arithmetical hierarchy in propositional dynamic logic
- An infinite hierarchy of temporal logics over branching time
- Future temporal logic needs infinitely many modalities
- Hierarchies of modal and temporal logics with reference pointers
- scientific article; zbMATH DE number 1678388 (Why is no real title available?)
- Extending Kamp's Theorem to Model Time Granularity
- Expressive completeness of temporal logic of trees
- Monadic Logic of Order over Naturals has no Finite Base
- A temporal logic for sortals
- On the expressive power of temporal logic for infinite words
- On the interpretability of arithmetic in temporal logic
This page was built for publication: Arity hierarchy for temporal logics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q944387)
