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 by Matz,...
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 by Matz,...
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...
Download Results (CSV)