Order-theoretic Trees: Monadic Second-order Descriptions and Regularity

DOI10.3233/FI-222120MaRDI QIDQ5038567zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 7 October 2022

Published in Fundamenta Informaticae (Search for Journal in Brave)

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

zbMATH Keywords

algebramonadic second-order logicorder-theoretic treeregular term

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Regularity equals monadic second-order definability for quasi-trees
• Algebraic and logical descriptions of generalized trees
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The monadic second-order logic of graphs. X: Linear orderings
• Regular languages of thin trees

Cites work

• Algebraic and logical descriptions of generalized trees
• Fields of logic and computation II. Essays dedicated to Yuri Gurevich on the occasion of his 75th birthday
• Finite automata and the logic of one-place predicates
• Fundamental properties of infinite trees
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 3675332 (Why is no real title available?)
• scientific article; zbMATH DE number 557977 (Why is no real title available?)
• scientific article; zbMATH DE number 1142319 (Why is no real title available?)
• Monadic second-order definable graph orderings
• On frontiers of regular trees
• On the structure of graphs in the Caucal hierarchy
• Several notions of rank-width for countable graphs
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
• Theory of relations. Transl. from the French by P. Clote. With an appendix by Norbert Sauer.

Cited in

(1)

• Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law

This page was built for publication: Order-theoretic Trees: Monadic Second-order Descriptions and Regularity

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