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
topHow 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.
- 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.
- V. Bruyère and O. Carton, Automata on linear orderings. J. Comput. System Sci.73 (2007) 1–24.
- 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.
- F. Hausdorff, Grundzüge einer Theorie der geordneten Mengen. Math. Ann.65 (1908) 435–505.
- S. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words. RAIRO Theoretical Informatics14 (1980) 131–141.
- 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.
- C. Rispal and O. Carton, Complementation of rational sets on countable scattered linear orderings. J. Found. Comput. Sci.16 (2005) 767–786.
- J.G. Rosenstein, Linear Orderings. Academic Press, New York (1982).
- W. Thomas, On frontiers of regular sets. RAIRO Theoretical Informatics20 (1986) 371–381.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.