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

DOI10.1109/LICS.2012.38MaRDI QIDQ2986804zbMATHOpenAlexFDO

Authors Viktor Engelmann, Stephan Kreutzer, Sebastian Siebertz

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

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)

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

Cited in

(8)

• Computations by fly-automata beyond monadic second-order logic
• Model checking for successor-invariant first-order logic on minor-closed graph classes
• Successor-invariant first-order logic on graphs with excluded topological subgraphs
• Fusion in relational structures and the verification of monadic second-order properties
• FO model checking on map graphs
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• Efficient First-Order Model-Checking Using Short Labels
• Model-checking on ordered structures

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)