Back to Search
Start Over
The “equal last letter” predicate for words on infinite alphabets and classes of multitape automata
- Source :
-
Theoretical Computer Science . Aug2009, Vol. 410 Issue 30-32, p2870-2884. 15p. - Publication Year :
- 2009
-
Abstract
- Abstract: We consider the first-order theory of the free infinitely generated monoid with the usual predicates “prefix” and “equal length” along with the predicate “equal last letter”. The associated definable relations are related to the algebras of relations recognized by different types of multitape automata which are natural extensions of the famous Rabin–Scott multitape automata and the synchronous automata. We investigate these classes of automata and solve decision issues concerning them. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 410
- Issue :
- 30-32
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 43177079
- Full Text :
- https://doi.org/10.1016/j.tcs.2009.01.034