Model-checking hierarchical structures
DOI10.1016/J.JCSS.2011.05.006zbMATH Open1279.68213OpenAlexW1980407685MaRDI QIDQ414908FDOQ414908
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Specification and verification (program logics, model checking, etc.) (68Q60) Logic in computer science (03B70)
Cites Work
- Title not available (Why is that?)
- Hyperedge replacement: grammars and languages
- 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
- Title not available (Why is that?)
- Existential second-order logic over graphs
- Elements of finite model theory.
- Title not available (Why is that?)
- Nondeterministic Space is Closed under Complementation
- Alternation
- Title not available (Why is that?)
- Decidability of DPDA equivalence
- Non-deterministic exponential time has two-prover interactive protocols
- The polynomial-time hierarchy
- Title not available (Why is that?)
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- Succinct representation, leaf languages, and projection reductions
- Languages represented by Boolean formulas
- Succinct representations of graphs
- A note on succinct representations of graphs
- Succinct circuit representations and leaf language classes are basically the same concept
- The method of forced enumeration for nondeterministic automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Deciding first-order properties of locally tree-decomposable structures
- The complexity of first-order and monadic second-order logic revisited
- A very hard log-space counting class
- The first order properties of products of algebraic systems
- Algorithmic uses of the Feferman-Vaught theorem
- Complete sets and the polynomial-time hierarchy
- Hierarchically specified unit disk graphs
- Succinctness as a source of complexity in logical formalisms
- Arity and alternation in second-order logic
- Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hierarchical planarity testing algorithms
- Title not available (Why is that?)
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- CONCUR 2003 - Concurrency Theory
- A uniform method for proving lower bounds on the computational complexity of logical theories
Cited In (10)
- On the complexity of the quantified bit-vector arithmetic with binary encoding
- Title not available (Why is that?)
- Testing hierarchical systems
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Mathematical Foundations of Computer Science 2004
- Title not available (Why is that?)
- Easy Problems for Grid-Structured Graphs
- Static correctness of hierarchical procedures
- Title not available (Why is that?)
- Title not available (Why is that?)
This page was built for publication: Model-checking hierarchical structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414908)
