Fixpoint logics over hierarchical structures
From MaRDI portal
Publication:2429724
DOI10.1007/s00224-009-9227-1zbMath1209.68320OpenAlexW2058101812MaRDI QIDQ2429724
Publication date: 1 April 2011
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-009-9227-1
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Algorithmic uses of the Feferman-Vaught theorem
- Hyperedge replacement: grammars and languages
- Elements of finite model theory.
- The complexity of tree automata and XPath on grammar-compressed trees
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- The polynomial-time hierarchy
- Hierarchically specified unit disk graphs
- Context-free graph grammars and concatenation of graphs
- Pushdown processes: Games and model-checking
- Automata, logics, and infinite games. A guide to current research
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Incremental model checking for decomposable structures
- Relational queries computable in polynomial time
- Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
- Alternation
- Application of model theoretic games to discrete linear orders and finite automata
- Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
- Hierarchical planarity testing algorithms
- Computer Aided Verification
- On model checking for the \(\mu\)-calculus and its fragments