Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On piecewise testable, starfree, and recognizable picture languages
| |
|
On piecewise testable, starfree, and recognizable picture languages
Oliver Matz1 
| (1) |
Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität Kiel, 24098 Kiel, Germany |
Abstract
We isolate a technique for showing that a picture language (i.e. a“two-dimensional language/rd) is not recognizable. Then
we prove the non-recognizability of a picture language that is both starfree (i.e., definable by means of union, concatenation,
and complement) and piecewise testable (i.e., definable by means of allowed subpictures), solving an open question in [GR96].
We also define local, locally testable, and locally threshold testable picture languages and summarize known inclusion results
for these classes. The classes of piecewise testable, locally testable, and locally threshold testable picture languages can,
as in the word case, be characterized by certain (fragments of) first-order logics.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|