Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334251 | Theoretical Computer Science | 2005 | 17 Pages |
Abstract
We consider a new operation on one-dimensional (resp. two-dimensional) word languages, obtained by piling up, one on top of the other, words of a given recognizable language (resp. two-dimensional recognizable language) on a previously empty one-dimensional (resp. two-dimensional) array. The resulting language is the set of words “seen from above”: a position in the array is labeled by the topmost letter. We show that in the one-dimensional case, the language is always recognizable. This is no longer true in the two-dimensional case which is shown by a counter-example, and we investigate in which particular cases the result may still hold.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Christian Choffrut, Berke Durak,