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

DOI10.3233/FI-222120OpenAlexW3211593247MaRDI QIDQ5038567FDOQ5038567

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

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

zbMATH Keywords

algebramonadic second-order logicregular termorder-theoretic tree

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

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

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)