Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences

DOI10.2168/LMCS-11(1:19)2015zbMath1392.03022arXiv1204.5194MaRDI QIDQ5246725

Jakub Gajarský, Petr Hliněný

Publication date: 22 April 2015

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.5194

zbMATH Keywords

MSO logicmodel checkingalgorithmic meta-theoremstree-depthCourcelle's theoremshrub-depth

Mathematics Subject Classification ID

Trees (05C05) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25)

Related Items (5)

Tree-depth and vertex-minors ⋮ Extended MSO model checking via small vertex integrity ⋮ Unnamed Item ⋮ Where First-Order and Monadic Second-Order Logic Coincide ⋮ Unnamed Item

This page was built for publication: Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences