Displaying similar documents to “Formal Languages - Concatenation and Closure”

Bidirectional string assembling systems

Martin Kutrib, Matthias Wendlandt (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We introduce and investigate several variants of a bidirectional string assembling system, which is a computational model that generates strings from copies of assembly units. The underlying mechanism is based on two-sided piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generative capacities and the relative power of the variants are our main interest. In particular, we prove that bidirectional string assembling system...

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