The paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-letter alphabet. The family DREC(1) of deterministic languages over a one-letter alphabet is characterized as both L(DOTA)(1), the class of languages accepted by deterministic on-line tessellation acceptors, and L(2AFA)(1), the class of languages recognized by 2-way alternating finite automata. We show that there are inherently ambiguous languages and unambiguously recognizable languages that cannot be deterministically recognized even in the case of a one-letter alphabet. In particular we show that on-line tessellation acceptors are more powerful than their deterministic counterpart, even in the case of a one-letter alphabet. Finally we show that DREC(1) is complex enough not to be characterized in terms of classical operations.
Deterministic and Unambiguous Two-dimensional Languages over One-letter Alphabet
ANSELMO, Marcella;
2009-01-01
Abstract
The paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-letter alphabet. The family DREC(1) of deterministic languages over a one-letter alphabet is characterized as both L(DOTA)(1), the class of languages accepted by deterministic on-line tessellation acceptors, and L(2AFA)(1), the class of languages recognized by 2-way alternating finite automata. We show that there are inherently ambiguous languages and unambiguously recognizable languages that cannot be deterministically recognized even in the case of a one-letter alphabet. In particular we show that on-line tessellation acceptors are more powerful than their deterministic counterpart, even in the case of a one-letter alphabet. Finally we show that DREC(1) is complex enough not to be characterized in terms of classical operations.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
