Abstract
Quasi-trees generalize trees in that the unique “path” between two nodes may be infinite and have any finite or countable order type, in particular that of rational numbers. They are used to define the rank-width of a countable graph in such a way that it is the least upper-bound of the rank-widths of its finite induced subgraphs. \(Join-trees \) are the corresponding directed “trees” and they are also useful to define the modular decomposition of a countable graph. We define algebras with finitely many operations that generate (via infinite terms) these generalized trees. We prove that the associated regular objects (those defined by regular terms) are exactly the ones definable by (i.e., are the unique models of) monadic second-order sentences. These results use and generalize a similar result by W. Thomas for countable linear orders.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Blumensath, A., Colcombet, T., Löding, C.: Logical theories and compatible operations. In: Flum, J., et al. (eds.) Logic and Automata: History and perspectives, pp. 73–106. Amsterdam University Press, Amsterdam (2008)
Courcelle, B.: Frontiers of infinite trees. ITA 12(4), 319–337 (1978). (former name of the journal: RAIRO Informatique théorique)
Courcelle, B.: Fundamental properties of infinite trees. Theor. Comput. Sci. 25, 95–169 (1983)
Courcelle, B.: Clique-width of countable graphs: a compactness property. Discrete Math. 276, 127–148 (2004)
Courcelle, B.: Several notions of rank-width for countable graphs (2014). (submitted)
Courcelle, B.: Algebras of quasi-trees (2015). (in preparation)
Courcelle, B., Delhommé, C.: The modular decomposition of countable graphs. Definition and construction in monadic second-order logic. Theor. Comput. Sci. 394, 1–38 (2008)
Courcelle, B., Engelfriet, J.: Graph structure and monadic second-order logic, a language theoretic approach. Cambridge University Press, Cambridge (2012)
Diestel, R.: Graph Theory, 4th edn. Springer-Verlag, Heidelberg (2010)
Heilbrunner, S.: An algorithm for the solution of fixed-point equations for infinite words. ITA 14, 131–141 (1980)
Kriz, I., Thomas, R.: Clique-sums, tree-decompositions and compactness. Discrete Math. 81, 177–185 (1990)
Oum, S.: Rank-width and vertex-minors. J. Comb. Theory, Ser. B 95, 79–100 (2005)
Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96, 514–528 (2006)
Thomas, W.: On frontiers of regular trees. ITA 20, 371–381 (1986)
Thomas, W.: Automata on infinite objects, in Handbook of Theoretical Computer Science, vol. B. Elsevier, Amsterdam (1990)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Courcelle, B. (2015). Regularity Equals Monadic Second-Order Definability for Quasi-trees. In: Beklemishev, L., Blass, A., Dershowitz, N., Finkbeiner, B., Schulte, W. (eds) Fields of Logic and Computation II. Lecture Notes in Computer Science(), vol 9300. Springer, Cham. https://doi.org/10.1007/978-3-319-23534-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-23534-9_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23533-2
Online ISBN: 978-3-319-23534-9
eBook Packages: Computer ScienceComputer Science (R0)