PDL for ordered trees

DOI10.3166/jancl.15.115-135zbMath1185.03056MaRDI QIDQ3647225

Bertrand Gaiffe, Loredana Afanasiev, Evan Goris, Ioanna Matilde Dimitriou, Maarten de Rijke, Patrick Blackburn, Maarten Marx

Publication date: 30 November 2009

Published in: Journal of Applied Non-Classical Logics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3166/jancl.15.115-135

zbMATH Keywords

complexity; definability; expressivity; ordered trees; propositional dynamic logic

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B45: Modal logic (including the logic of norms)

03B70: Logic in computer science

68Q60: Specification and verification (program logics, model checking, etc.)

Related Items

2-Exp Time lower bounds for propositional dynamic logics with intersection, Complexity of hybrid logics over transitive frames, Inessential features, ineliminable features, and modal logics for model theoretic syntax, Complexity of modal logics with Presburger constraints, Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization, Efficiently Deciding μ-Calculus with Converse over Finite Trees, PDL with intersection and converse: satisfiability and infinite-state model checking

Cites Work

• Unnamed Item
• Unnamed Item
• Handbook of philosophical logic. Volume II: Extensions of classical logic
• Automata-theoretic techniques for modal logics of programs
• Propositional dynamic logic of regular programs
• Syntactic codes and grammar refinement
• Linguistics, Logic and Finite Trees
• Decidability of S1S and S2S
• Reachability logic: an efficient fragment of transitive closure logic
• A Modal Perspective on Path Constraints