6533b824fe1ef96bd12814b5

RESEARCH PRODUCT

Unambiguous recognizable two-dimensional languages

Antonio RestivoDora GiammarresiMarcella AnselmoMaria Madonia

subject

DeterminismSettore INF/01 - InformaticaDeterministic context-free languageGeneral MathematicsTwo-dimensional languagesAutomata and formal languages; Determinism; Two-dimensional languages; UnambiguityComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Class (philosophy)Computer Science ApplicationsUndecidable problemAutomata and Formal Languages. ; Unambiguity ; Determinism. .; Two-dimensional languagesCombinatoricsClosure (mathematics)Computer Science::Programming LanguagesAutomata and formal languagesDeterminism.ArithmeticComputer Science::Formal Languages and Automata TheorySoftwareUnambiguityMathematics

description

We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure properties of UREC are presented. Finally we show that it is undecidable whether a given tiling system is unambiguous.

yearjournalcountryeditionlanguage
2006-04-01
http://hdl.handle.net/10447/6466