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 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

MADONIA, Maria Serafina
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 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.
Two-dimensional languages; Unambiguity ; One-letter alphabet. ; Determinism; Finite Automata
File in questo prodotto:
File Dimensione Formato  
TCS2009JournalCAI07.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Dimensione 641.02 kB
Formato Adobe PDF
641.02 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/4947
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 13
social impact