×

Deterministic and unambiguous two-dimensional languages over one-letter alphabet. (English) Zbl 1162.68020

Summary: The paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-letter alphabet. The family DREC(1) of deterministic languages over a one-letter alphabet is characterized as both \(\mathcal L\)(DOTA)\((1)\), the class of languages accepted by deterministic on-line tessellation acceptors, and \(\mathcal L\)(2AFA)\((1)\), the class of languages recognized by 2-way alternating finite automata. We show that there are inherently ambiguous languages and unambiguously recognizable languages that cannot be deterministically recognized even in the case of a one-letter alphabet. In particular we show that on-line tessellation acceptors are more powerful than their deterministic counterpart, even in the case of a one-letter alphabet. Finally we show that DREC(1) is complex enough not to be characterized in terms of classical operations.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anselmo, M.; Madonia, M., Deterministic two-dimensional languages over one-letter alphabet, (Bozapalidis, S.; Rahonis, G., Procs. CAI 07. Procs. CAI 07, LNCS, vol. 4728 (2007), Springer-Verlag: Springer-Verlag Berlin Heidelberg), 147-159 · Zbl 1148.68395
[2] Anselmo, M.; Giammarresi, D.; Madonia, M., From determinism to non-determinism in recognizable two-dimensional languages, (Procs. DLT 07. Procs. DLT 07, LNCS, vol. 4588 (2007), Springer Verlag), 36-47 · Zbl 1202.68218
[3] Anselmo, M.; Giammarresi, D.; Madonia, M., New operators and regular expressions for two-dimensional languages over one-letter alphabet, Theoret. Comput. Sci., 340, 2, 408-431 (2005) · Zbl 1078.68072
[4] Anselmo, M.; Giammarresi, D.; Madonia, M.; Restivo, A., Unambiguous recognizable two-dimensional languages, (RAIRO: Theoretical Informatics and Applications, 40(2) (2006), EDP Sciences), 227-294 · Zbl 1112.68085
[5] Bertoni, A.; Goldwurm, M.; Lonati, V., On the complexity of unary tiling-recognizable picture languages, (Proc. STACS 07. Proc. STACS 07, LNCS, vol. 4393 (2007), Springer Verlag), 381-392 · Zbl 1159.68473
[6] M. Blum, C. Hewitt, Automata on a two-dimensional tape, in: IEEE Symposium on Switching and Automata Theory, 1967, pp. 155-160; M. Blum, C. Hewitt, Automata on a two-dimensional tape, in: IEEE Symposium on Switching and Automata Theory, 1967, pp. 155-160
[7] Eilenberg, S., Automata, Languages and Machines, vol. A (1974), Academic Press · Zbl 0317.94045
[8] Eilenberg, S.; Schützenberger, M. P., Rational sets in commutative monoids, J. Algebra, 13, 2, 173-191 (1969) · Zbl 0206.02703
[9] Giammarresi, D., Two-dimensional languages and recognizable functions, (Rozenberg, G.; Salomaa, A., Procs. in Dev. on Language Theory 1993 (1994), World Scientific Publishing Co.), 290-301
[10] Giammarresi, D.; Restivo, A., Recognizable picture languages, Int. J. Pattern Recognit. Artif. Intell., 6, 2 & 3, 241-256 (1992)
[11] Giammarresi, D.; Restivo, A., Two-dimensional languages, (Rozenberg, G.; etal., Handbook of Formal Languages, vol. III (1997), Springer Verlag), 215-268
[12] Giammarresi, D.; Restivo, A., Matrix-based complexity functions and recognizable picture languages, (Grädel, E.; Flum, J.; Wilke, T., Logic and Automata: History and Perspectives. Logic and Automata: History and Perspectives, Texts in Logic and Games, vol. 2 (2007), Amsterdam University Press), 315-337
[13] Inoue, K.; Nakamura, A., Some properties of two-dimensional on-line tessellation acceptors, Inform. Sci., 13, 95-121 (1977) · Zbl 0371.94067
[14] Inoue, K.; Nakamura, A., Two-dimensional finite automata and unacceptable functions, Intern. J. Comput. Math., 7, 207-213 (1979), Sec. A · Zbl 0415.68022
[15] Ito, A.; Inoue, K.; Takanami, I., Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through \(180^∘\)-rotation, Theoret. Comput. Sci., 66, 273-287 (1989) · Zbl 0679.68104
[16] Inoue, K.; Takanami, I., A characterization of recognizable picture languages, (Nakamura, A.; etal., Proc. Second International Colloquium on Parallel Image Processing. Proc. Second International Colloquium on Parallel Image Processing, LNCS, vol. 654 (1993), Springer-Verlag: Springer-Verlag Berlin)
[17] Inoue, K.; Takanami, I.; Taniguchi, H., Two-dimensional alternating turing machines, Theoret. Comput. Sci., 27, 61-83 (1983) · Zbl 0539.68039
[18] Lindgren, K.; Moore, C.; Nordahl, M., Complexity of two-dimensional patterns, J. Stat. Phys., 91, 5-6, 909-951 (1998) · Zbl 0917.68156
[19] Kari, J.; Moore, C., Rectangles and squares recognized by two-dimensional automata, (Karhumaki; etal., Theory is Forever. Theory is Forever, Lecture Notes in Computer Science, vol. 3113 (2004), Springer Verlag), 134-144 · Zbl 1055.68071
[20] Kinber, E. B., (Three-way Automata on Rectangular Tapes over a One-Letter Alphabet. Three-way Automata on Rectangular Tapes over a One-Letter Alphabet, Information Sciences, vol. 35 (1985), Elsevier Sc. Publ.), 61-77 · Zbl 0592.68051
[21] Matz, O., Regular expressions and context-free grammars for picture languages, (Proc. STACS’97. Proc. STACS’97, LNCS, vol. 1200 (1997), Springer Verlag), 283-294 · Zbl 1498.68139
[22] O. Matz, Dot-depth and monadic quantifier alternation over pictures, Ph.D. Thesis, Technical Report 99-08, RWTH Aachen, 1999; O. Matz, Dot-depth and monadic quantifier alternation over pictures, Ph.D. Thesis, Technical Report 99-08, RWTH Aachen, 1999 · Zbl 0938.68501
[23] Matz, O., Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures, Theoretical Computer Science, 270, 1-2, 1-70 (2002) · Zbl 0992.68128
[24] Matz, O., Recognizable vs. regular picture languages, (Bozapalidis, S.; Rahonis, G., Procs. CAI 07. Procs. CAI 07, LNCS, vol. 4728 (2007), Springer-Verlag: Springer-Verlag Berlin Heidelberg) · Zbl 1147.68045
[25] Mäurer, I., Weighted picture automata and weighted logics, (Durand, B.; Thomas, W., Procs. STACS 2006. Procs. STACS 2006, LNCS, vol. 3885 (2006), Springer-Verlag), 313-324 · Zbl 1136.68421
[26] Potthoff, A.; Seibert, S.; Thomas, W., Nondeterminism versus determinism of finite automata over directed acyclic graphs, Bull. Belgian Math. Soc., 1, 285-298 (1994) · Zbl 0803.68032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.