We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
TREE AUTOMATA AND AUTOMATA ON LINEAR ORDERINGS.
- Authors
Véronique Bruyère; Carton, Olivier; Sénizergues, Géraud
- 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].
- Subjects
LINEAR orderings; SEQUENTIAL machine theory; SET theory; MACHINE theory; COMPUTERS
- Publication
RAIRO - Theoretical Informatics & Applications, 2009, Vol 43, Issue 2, p321
- ISSN
2804-7346
- Publication type
Article
- DOI
10.1051/ita/2009009