About: Unambiguous recognizable two-dimensional languages

Documentation

scienceplus.abes.fr version Bêta

scienceplus.abes.fr | explorer

À propos de : Unambiguous recognizable two-dimensional languages Goto Sponge NotDistinct Permalink

Attributs	Valeurs
type	work Article
Is Part Of	Alberto Bertoni: Climbing summits
Subject	determinism unambiguity Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) Formal languages and automata Automata and formal languages two-dimensional languages.
Title	Unambiguous recognizable two-dimensional languages
Date	2006-01-01(xsd:dateTime)
has manifestation of work	http://hub.abes.fr/edp/periodical/ita/2006/volume_40/issue_2/ita06024/m/print http://hub.abes.fr/edp/periodical/ita/2006/volume_40/issue_2/ita06024/m/web
related by	http://hub.abes.fr/edp/periodical/ita/2006/volume_40/issue_2/ita06024/authorship/4 http://hub.abes.fr/edp/periodical/ita/2006/volume_40/issue_2/ita06024/authorship/3 http://hub.abes.fr/edp/periodical/ita/2006/volume_40/issue_2/ita06024/authorship/1 http://hub.abes.fr/edp/periodical/ita/2006/volume_40/issue_2/ita06024/authorship/2
Author	Restivo, Antonio Giammarresi, Dora Madonia, Maria Anselmo, Marcella
Abstract	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.
article type	research-article
publisher identifier	ita06024
Date Copyrighted	2006-01-01(xsd:dateTime)
Rights	© EDP Sciences, 2006
Rights Holder	EDP Sciences
is part of this journal	RAIRO - Theoretical Informatics and Applications
is primary topic of	http://hub.abes.fr/edp/periodical/ita/2006/volume_40/issue_2/ita06024/w/record

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata