# Tree Automata and Automata on Linear Orderings

Véronique Bruyère; Olivier Carton; Géraud Sénizergues

RAIRO - Theoretical Informatics and Applications (2009)

- Volume: 43, Issue: 2, page 321-338
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBruyère, Véronique, Carton, Olivier, and Sénizergues, Géraud. "Tree Automata and Automata on Linear Orderings." RAIRO - Theoretical Informatics and Applications 43.2 (2009): 321-338. <http://eudml.org/doc/250607>.

@article{Bruyère2009,

abstract = {
We show that the inclusion problem is decidable for rational languages
of words indexed by scattered countable linear orderings. The method leans on a reduction to
the decidability of the monadic second order theory of the infinite binary tree
[9].
},

author = {Bruyère, Véronique, Carton, Olivier, Sénizergues, Géraud},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Finite automata; words over linear orderings-trees; monadic second order logics.; finite automata; words over linear orderings; trees; monadic second-order logic},

language = {eng},

month = {4},

number = {2},

pages = {321-338},

publisher = {EDP Sciences},

title = {Tree Automata and Automata on Linear Orderings},

url = {http://eudml.org/doc/250607},

volume = {43},

year = {2009},

}

TY - JOUR

AU - Bruyère, Véronique

AU - Carton, Olivier

AU - Sénizergues, Géraud

TI - Tree Automata and Automata on Linear Orderings

JO - RAIRO - Theoretical Informatics and Applications

DA - 2009/4//

PB - EDP Sciences

VL - 43

IS - 2

SP - 321

EP - 338

AB -
We show that the inclusion problem is decidable for rational languages
of words indexed by scattered countable linear orderings. The method leans on a reduction to
the decidability of the monadic second order theory of the infinite binary tree
[9].

LA - eng

KW - Finite automata; words over linear orderings-trees; monadic second order logics.; finite automata; words over linear orderings; trees; monadic second-order logic

UR - http://eudml.org/doc/250607

ER -

## References

top- V. Bruyère and O. Carton, Automata on linear orderings, edited by J. Sgall, A. Pultr and P. Kolman, MFCS'2001. Lect. Notes Comput. Sci.2136 (2001) 236–247. Zbl0999.68100
- V. Bruyère, O. Carton and G. Sénizergues, Tree automata and automata on linear orderings, in Proceedings WORDS'03. Lect. Notes Comput. Sci.27 (2003) 222–231. TUCS General Publication. Zbl1040.68072
- V. Bruyère and O. Carton, Automata on linear orderings. J. Comput. System Sci.73 (2007) 1–24. Zbl1178.68307
- O. Carton, Accessibility in automata on scattered linear orderings, edited by K. Diks and W. Rytter, MFCS'2002. Lect. Notes Comput. Sci.2420 (2002) 155–164.
- B. Courcelle, Frontiers of infinite trees. RAIRO Theoretical Informatics12 (1978) 319–337. Zbl0411.68065
- F. Hausdorff, Grundzüge einer Theorie der geordneten Mengen. Math. Ann.65 (1908) 435–505. Zbl39.0099.01
- S. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words. RAIRO Theoretical Informatics14 (1980) 131–141. Zbl0433.68062
- S.C. Kleene, Representation of events in nerve nets and finite automata, edited by C.E. Shannon, Automata studies, 3–41. Princeton University Press, Princeton (1956).
- M.O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc.141 (1969) 1–35. Zbl0221.02031
- C. Rispal and O. Carton, Complementation of rational sets on countable scattered linear orderings. J. Found. Comput. Sci.16 (2005) 767–786. Zbl1161.68551
- J.G. Rosenstein, Linear Orderings. Academic Press, New York (1982).
- W. Thomas, On frontiers of regular sets. RAIRO Theoretical Informatics20 (1986) 371–381. Zbl0639.68071

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.