Displaying similar documents to “On Varieties of Literally Idempotent Languages”

Classes of two-dimensional languages and recognizability conditions

Marcella Anselmo, Maria Madonia (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

The paper deals with some classes of two-dimensional recognizable languages of “high complexity”, in a sense specified in the paper and motivated by some necessary conditions holding for recognizable and unambiguous languages. For such classes we can solve some open questions related to unambiguity, finite ambiguity and complementation. Then we reformulate a necessary condition for recognizability stated by Matz, introducing a new complexity function. We solve an open question proposed...

Unambiguous recognizable two-dimensional languages

Marcella Anselmo, Dora Giammarresi, Maria Madonia, Antonio Restivo (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

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