An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning

DOI10.1007/978-3-030-45231-5_24zbMath1506.03076OpenAlexW3016818860MaRDI QIDQ5918962

Alessio Mansutti

Publication date: 23 September 2020

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-45231-5_24

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

On Composing Finite Forests with Modal Logics ⋮ Unnamed Item ⋮ An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the almighty wand
• Elements of finite model theory.
• Adjunct elimination in context logic for trees
• Borel determinacy
• Propositional dynamic logic of regular programs
• The effects of adding reachability predicates in propositional separation logic
• Separation logic with one quantified variable
• Complexity Hierarchies beyond Elementary
• The Complexity of Clausal Fragments of LTL
• Quantified CTL: Expressiveness and Complexity
• Two-Variable Separation Logic and Its Inner Circle
• Sabotage Modal Logic: Some Model and Proof Theoretic Aspects
• The Birth of Model Checking
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• Separating Graph Logic from MSO
• The complexity of propositional linear temporal logics
• Using the Universal Modality: Gains and Questions
• Propositional quantifiers in modal logic1
• The Logic of Bunched Implications
• Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
• The Complexity of Satisfiability for Fragments of CTL and CTL⋆
• Global and Local Graph Modifiers
• The Impact of Including Model Update Operators in Modal Logics
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Decidability of Second-Order Theories and Automata on Infinite Trees
• A Road Map of Interval Temporal Logics and Duration Calculi

This page was built for publication: An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning