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

Abstract

top
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].

How to cite

top

Bruyè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
  1. 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
  2. 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
  3. V. Bruyère and O. Carton, Automata on linear orderings. J. Comput. System Sci.73 (2007) 1–24.  Zbl1178.68307
  4. 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.  
  5. B. Courcelle, Frontiers of infinite trees. RAIRO Theoretical Informatics12 (1978) 319–337.  Zbl0411.68065
  6. F. Hausdorff, Grundzüge einer Theorie der geordneten Mengen. Math. Ann.65 (1908) 435–505.  Zbl39.0099.01
  7. S. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words. RAIRO Theoretical Informatics14 (1980) 131–141.  Zbl0433.68062
  8. 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).  
  9. M.O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc.141 (1969) 1–35.  Zbl0221.02031
  10. C. Rispal and O. Carton, Complementation of rational sets on countable scattered linear orderings. J. Found. Comput. Sci.16 (2005) 767–786.  Zbl1161.68551
  11. J.G. Rosenstein, Linear Orderings. Academic Press, New York (1982).  
  12. W. Thomas, On frontiers of regular sets. RAIRO Theoretical Informatics20 (1986) 371–381.  Zbl0639.68071

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.