Nonlinear Sciences – Cellular Automata and Lattice Gases
Scientific paper
2010-12-03
Nonlinear Sciences
Cellular Automata and Lattice Gases
Journ\'ees Automates Cellulaires 2010, Turku : Finland (2010)
Scientific paper
Tiling recognizable two-dimensional languages, also known as REC, generalize recognizable string languages to two dimensions and share with them several theoretical properties. Nevertheless REC is not closed under complementation and the membership problem is NP-complete. This implies that this family REC is intrinsically non-deterministic. The natural and immediate definition of unambiguity corresponds to a family UREC of languages that is strictly contained in REC. On the other hand this definition of unambiguity leads to an undecidability result and therefore it cannot correspond to any deterministic notion. We introduce the notion of line-unambiguous tiling recognizable languages and prove that it corresponds or somehow naturally introduces different notions of determin- ism that define a hierarchy inside REC.
No associations
LandOfFree
Tiling-Recognizable Two-Dimensional Languages: From Non-Determinism to Determinism through Unambiguity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Tiling-Recognizable Two-Dimensional Languages: From Non-Determinism to Determinism through Unambiguity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tiling-Recognizable Two-Dimensional Languages: From Non-Determinism to Determinism through Unambiguity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-514616