First-order and monadic second-order model-checking on ordered structures

DOI10.1109/LICS.2012.38zbMATH Open1362.68167OpenAlexW2083568668MaRDI QIDQ2986804FDOQ2986804

Viktor Engelmann, Sebastian Siebertz, Stephan Kreutzer

Publication date: 16 May 2017

Published in: 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/lics.2012.38

Recommendations

• Model-checking on ordered structures
• Model checking for successor-invariant first-order logic on minor-closed graph classes
• Successor-invariant first-order logic on graphs with excluded topological subgraphs
• scientific article; zbMATH DE number 7297863
• The complexity of first-order and monadic second-order logic revisited

zbMATH Keywords

finite model theorymodel theoryalgorithmic meta-theoremsorder-invariant first-order logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Model theory of finite structures (03C13) Specification and verification (program logics, model checking, etc.) (68Q60) Classical first-order logic (03B10) Basic properties of first-order languages and structures (03C07) Descriptive complexity and finite models (68Q19)

Cited In (4)

• Efficient First-Order Model-Checking Using Short Labels
• Computations by fly-automata beyond monadic second-order logic
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• Fusion in relational structures and the verification of monadic second-order properties

This page was built for publication: First-order and monadic second-order model-checking on ordered structures

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