Fixpoint logics over hierarchical structures

DOI10.1007/S00224-009-9227-1MaRDI QIDQ2429724zbMATH OpenOpenAlexFDO

Authors Stefan Göller, Markus Lohrey

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

zbMATH Keywords

\(\mu\)-calculuscomplexityhierarchical structuresmodel-checkingparity games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Model-checking hierarchical structures
• Improved model checking of hierarchical systems
• Improved model checking of hierarchical systems
• Mathematical Foundations of Computer Science 2005

Cites work

• Algorithmic uses of the Feferman-Vaught theorem
• Alternation
• Application of model theoretic games to discrete linear orders and finite automata
• Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
• Automata, logics, and infinite games. A guide to current research
• Context-free graph grammars and concatenation of graphs
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
• Elements of finite model theory.
• Fast mu-calculus model checking when tree-width is bounded.
• Hierarchical planarity testing algorithms
• Hierarchically specified unit disk graphs
• scientific article; zbMATH DE number 1670767 (Why is no real title available?)
• scientific article; zbMATH DE number 515730 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 2080197 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• scientific article; zbMATH DE number 751134 (Why is no real title available?)
• scientific article; zbMATH DE number 873906 (Why is no real title available?)
• scientific article; zbMATH DE number 1408351 (Why is no real title available?)
• Hyperedge replacement: grammars and languages
• Incremental model checking for decomposable structures
• On model checking for the -calculus and its fragments
• Pushdown processes: Games and model-checking
• Relational queries computable in polynomial time
• 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 monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The polynomial-time hierarchy

Cited in

(10)

• Space-efficient fragments of higher-order fixpoint logic
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• Hierarchies in Dependence Logic
• Improved model checking of hierarchical systems
• Model-checking hierarchical structures
• Improved model checking of hierarchical systems
• scientific article; zbMATH DE number 1256653 (Why is no real title available?)
• scientific article; zbMATH DE number 1078383 (Why is no real title available?)
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• FO-query enumeration over SLP-compressed structures of bounded degree

This page was built for publication: Fixpoint logics over hierarchical structures

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