Model-checking hierarchical structures
From MaRDI portal
Publication:414908
DOI10.1016/j.jcss.2011.05.006zbMath1279.68213MaRDI QIDQ414908
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
68Q25: Analysis of algorithms and problem complexity
03B70: Logic in computer science
68Q60: Specification and verification (program logics, model checking, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
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
