Boundedness of Monadic FO over Acyclic Structures

DOI10.1007/978-3-540-73420-8_50MaRDI QIDQ5428840zbMATH OpenOpenAlexFDO

Authors Stephan Kreutzer, Martin Otto, Nicole Schweikardt

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_50

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Recommendations

• Decidability results for the boundedness problem
• The complexity of boundedness for guarded logics
• Monadic second order finite satisfiability and unbounded tree-width
• A unified approach to boundedness properties in MSO
• Automatic structures of bounded degree

Cited in

(2)

• On the complexity of decision using destinies in \(H\)-bounded structures
• Decidability results for the boundedness problem

This page was built for publication: Boundedness of Monadic FO over Acyclic Structures

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