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

• Autorzy: Courcelle Bruno

Identyfikatory

DOI

10.3233/FI-222120

• Języki publikacji: EN

Abstrakty

EN

An order-theoretic forest is a countable partial order such that the set of elements larger than any element is linearly ordered. It is an order-theoretic tree if any two elements have an upper-bound. The order type of a branch can be any countable linear order. Such generalized infinite trees yield convenient definitions of the rank-width and the modular decomposition of countable graphs. We define an algebra based on only four operations that generate up to isomorphism and via infinite terms these order-theoretic trees and forests. We prove that the associated regular objects, those defined by regular terms, are exactly the ones that are the unique models of monadic second-order sentences.

Słowa kluczowe

EN

order-theoretic tree; algebra; regular term; monadic second-order logic.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 186, nr 1-4
• Strony: 89--120
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Courcelle Bruno

• Bordeaux University, CNRS, LaBRI, France

Bibliografia

• [1] Angluin D. Local and global properties in networks of processors (extended abstract). Proceedings Symp. on Theory of Computing, 1980, pp. 82-93.
• [2] Arnold A. Finite transition systems, Prentice-Hall, 1994 (translated from French by J. Plaice). ISBN: 0130929905, 9780130929907.
• [3] Bloem R, Chatterjee K, and Jobstmann B. Games and synthesis. In: Handbook of Model-Checking. Springer, 2014.
• [4] Blumensath A. On the structure of graphs in the Caucal hierarchy. Theor. Comput. Sci. 2008. 400(1-3):19-45. doi:10.1016/j.tcs.2008.01.053.
• [5] Blumensath A, and Courcelle B. Monadic second-order definable graph orderings. Logical Methods in Computer Science 2014. 10(1-2)1-36.
• [6] Courcelle B. Frontiers of infinite trees. ITA (Informatique Th´eorique et Applications) (former name of the journal: RAIRO Informatique th´eorique). 1978. 12(4):317-339. URL http://www.numdam.org/item?id=ITA 1978 12 4 319 0.
• [7] Courcelle B. Fundamental properties of infinite trees. Theor. Comput. Sci. 1983. 25(2):95-169. doi:10.1016/0304-3975(83)90059-2.
• [8] Courcelle B. Recursive applicative program schemes, in Handbook of Theoretical Computer Science, vol. B, Elsevier, 1990, pp. 459-492.
• [9] Courcelle B. Several notions of rank-width for countable graphs, J. Combinatorial Theory B 2017. 123:186-214. doi:10.1016/j.jctb.2016.12.002.
• [10] Courcelle B. Regularity equals monadic second-order definability for quasi-trees, in Fields of Logic and Computation II, Lec. Notes Comput. Sci. vol. 9300. (2015) pp. 129-141. doi:10.1007/978-3-319-23534-9 7.
• [11] Courcelle B. Algebraic and logical descriptions of generalized trees, Logical Methods in Computer Science. 2017. 13 (3):1-39. URL https://hal.archives-ouvertes.fr/hal-01299077v3.
• [12] Courcelle B, and Delhommé C. The modular decomposition of countable graphs. Definition and construction in monadic second-order logic. Theor. Comput. Sci.. 2008. 394(1-2):1-38. doi:10.1016/j.tcs.2007.10.046.
• [13] Courcelle B, and Engelfriet J. Graph structure and monadic second-order logic, a language theoretic approach, Cambridge University Press, 2012. ISBN-10:0521898331, 13:978-0521898331.
• [14] Courcelle B, and Métivier Y. Unfoldings and coverings of weighted graphs, 2020, submitted for publication. URL https://hal.archives-ouvertes.fr/hal-02559494.
• [15] Fraïssé R. Theory of relations, Studies in Logic, Volume 145, North-Holland, 2000. ISBN: 9780444505422, 9780080519111.
• [16] Heilbrunner S. An algorithm for the solution of fixed-point equations for infinite words. ITA 1980. 14:131-141. URL https://www.rairo-ita.org/articles/ita/abs/1980/02/ita1980140201311/ita1980140201311.html
• [17] Thomas W. On frontiers of regular trees. ITA. 1986. 20:371-381. URL https://www.rairo-ita.org/articles/ita/abs/1986/04/ita1986200403711/ita1986200403711.html
• [18] Thomas W. Languages, automata, and logic. In: Rozenberg and Salomaa (eds.), Handbook of Formal Language Theory, vol. III, Springer, 1997, pp. 389-455. ISBN:9783540604204.
• [19] Trakhtenbrot B. Finite automata and the logic of one-place predicates, Sib. Math. J., 3 (1962) 103-131, English translation : AMS Transl. 59 (1966) 23-55. URL http://mi.mathnet.ru/eng/dan/ v140/ i2/p326.
• [20] Vardi M, and Wilke T. Automata: from logics to algorithms. In: Flum, Graedel and Wilke (eds.), Logic and Automata, Texts in Logic and Games, vol. 2. Amsterdam University Press, 2007.