Model-checking hierarchical structures

DOI10.1016/j.jcss.2011.05.006zbMath1279.68213OpenAlexW1980407685MaRDI QIDQ414908

Markus Lohrey

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.05.006

zbMATH Keywords

complexitymodel-checkinglogic in computer sciencehierarchical structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

On the complexity of the quantified bit-vector arithmetic with binary encoding ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Languages represented by Boolean formulas
• Algorithmic uses of the Feferman-Vaught theorem
• Succinct circuit representations and leaf language classes are basically the same concept
• Hyperedge replacement: grammars and languages
• Non-deterministic exponential time has two-prover interactive protocols
• Elements of finite model theory.
• A uniform method for proving lower bounds on the computational complexity of logical theories
• The method of forced enumeration for nondeterministic automata
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• A very hard log-space counting class
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Hierarchically specified unit disk graphs
• Succinct representation, leaf languages, and projection reductions
• Succinctness as a source of complexity in logical formalisms
• The complexity of first-order and monadic second-order logic revisited
• Arity and alternation in second-order logic
• Relationships between nondeterministic and deterministic tape complexities
• On uniformity within \(NC^ 1\)
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Deciding first-order properties of locally tree-decomposable structures
• The first order properties of products of algebraic systems
• Succinct representations of graphs
• Nondeterministic Space is Closed under Complementation
• Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
• Alternation
• Complexity classes and theories of finite models
• Application of model theoretic games to discrete linear orders and finite automata
• Expressibility and Parallel Complexity
• Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
• Hierarchical planarity testing algorithms
• A note on succinct representations of graphs
• Existential second-order logic over graphs
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• CONCUR 2003 - Concurrency Theory
• Decidability of DPDA equivalence

This page was built for publication: Model-checking hierarchical structures