Model-checking hierarchical structures

DOI10.1016/J.JCSS.2011.05.006MaRDI QIDQ414908zbMATH OpenOpenAlexFDO

Authors 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

complexitylogic in computer sciencehierarchical structuresmodel-checking

Mathematics Subject Classification ID

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)

Recommendations

• Fixpoint logics over hierarchical structures
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Improved model checking of hierarchical systems
• Improved model checking of hierarchical systems
• scientific article; zbMATH DE number 1290983

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1335887 (Why is no real title available?)
• scientific article; zbMATH DE number 1351076 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 751134 (Why is no real title available?)
• A note on succinct representations of graphs
• A uniform method for proving lower bounds on the computational complexity of logical theories
• A very hard log-space counting class
• 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
• Arity and alternation in second-order logic
• Complete sets and the polynomial-time hierarchy
• Complexity classes and theories of finite models
• Decidability of DPDA equivalence
• Deciding first-order properties of locally tree-decomposable structures
• Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
• Elements of finite model theory.
• Existential second-order logic over graphs: charting the tractability frontier
• Expressibility and Parallel Complexity
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Hierarchical planarity testing algorithms
• Hierarchically specified unit disk graphs
• Hyperedge replacement: grammars and languages
• Languages represented by Boolean formulas
• Model checking a path (preliminary report)
• Non-deterministic exponential time has two-prover interactive protocols
• Nondeterministic Space is Closed under Complementation
• On uniformity within \(NC^ 1\)
• Relationships between nondeterministic and deterministic tape complexities
• Succinct circuit representations and leaf language classes are basically the same concept
• Succinct representation, leaf languages, and projection reductions
• Succinct representations of graphs
• Succinctness as a source of complexity in logical formalisms
• The complexity of first-order and monadic second-order logic revisited
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• The first order properties of products of algebraic systems
• The method of forced enumeration for nondeterministic automata
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The polynomial-time hierarchy

Cited in

(11)

• Mathematical Foundations of Computer Science 2004
• Testing hierarchical systems
• scientific article; zbMATH DE number 5636822 (Why is no real title available?)
• Fixpoint logics over hierarchical structures
• On quantified propositional logics and the exponential time hierarchy
• On the complexity of the quantified bit-vector arithmetic with binary encoding
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Easy Problems for Grid-Structured Graphs
• Static correctness of hierarchical procedures
• scientific article; zbMATH DE number 7453971 (Why is no real title available?)
• scientific article; zbMATH DE number 1852146 (Why is no real title available?)

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)