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

DOI10.1109/LICS.2012.38MaRDI QIDQ2986804zbMATH OpenOpenAlexFDO

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

algorithmic meta-theoremsfinite model theorymodel theoryorder-invariant first-order logic

Mathematics Subject Classification ID

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

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)

• FO model checking on map graphs
• Fusion in relational structures and the verification of monadic second-order properties
• Efficient First-Order Model-Checking Using Short Labels
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• 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
• Computations by fly-automata beyond monadic second-order logic

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)