A logical approach to locality in pictures languages. (English) Zbl 1342.68183
Summary: This paper deals with descriptive complexity of picture languages of any dimension by fragments of existential second-order logic:
1) We generalize to any dimension the characterization by D. Giammarresi et al. [Inf. Comput. 125, No. 1, 32–45 (1996; Zbl 0853.68131)] of the class of recognizable picture languages in existential monadic second-order logic.
2) We state natural logical characterizations of the class of picture languages of any dimension \(d \geq 1\) recognized in linear time on nondeterministic cellular automata, a robust complexity class that contains, for \(d = 1\), all the natural NP-complete problems. Our characterizations are essentially deduced from normalization results for first-order and existential second-order logics over pictures.
1) We generalize to any dimension the characterization by D. Giammarresi et al. [Inf. Comput. 125, No. 1, 32–45 (1996; Zbl 0853.68131)] of the class of recognizable picture languages in existential monadic second-order logic.
2) We state natural logical characterizations of the class of picture languages of any dimension \(d \geq 1\) recognized in linear time on nondeterministic cellular automata, a robust complexity class that contains, for \(d = 1\), all the natural NP-complete problems. Our characterizations are essentially deduced from normalization results for first-order and existential second-order logics over pictures.
MSC:
| 68Q45 | Formal languages and automata |
| 03B15 | Higher-order logic; type theory (MSC2010) |
| 03D05 | Automata and formal grammars in connection with logical questions |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q80 | Cellular automata (computational aspects) |
Keywords:
picture languages; locality and tiling; recognizability; linear time; cellular automata; logical characterizations; monadic second-order logic; existential second-order logicCitations:
Zbl 0853.68131References:
| [1] | Barbanchon, R.; Grandjean, E., Local problems, planar local problems and linear time, (Bradfield, J. C., CSL. CSL, Lect. Notes Comput. Sci., vol. 2471 (2002), Springer), 397-411 · Zbl 1020.68038 |
| [2] | Borchert, B., Formal language characterizations of P, NP, and PSPACE, J. Autom. Lang. Comb., 13, 3/4, 161-183 (2008) · Zbl 1191.68332 |
| [3] | Börger, E.; Grädel, E.; Gurevich, Y., The Classical Decision Problem (2001), Springer, Universitext, 482 pages · Zbl 0970.03001 |
| [4] | Büchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Log. Grundl. Math., 6, 66-92 (1960) · Zbl 0103.24705 |
| [5] | Cook, S. A., A hierarchy for nondeterministic time complexity, (Fischer, P. C.; Zeiger, H. P.; Ullman, J. D.; Rosenberg, A. L., STOC (1972), ACM), 187-192 · Zbl 0361.68074 |
| [6] | Courcelle, B.; Engelfriet, J., Graph Structure and Monadic Second-Order Logic, a Language Theoretic Approach (2012), Cambridge University Press · Zbl 1257.68006 |
| [7] | (Delorme, M.; Mazoyer, J., Cellular Automata: a Parallel Model. Cellular Automata: a Parallel Model, Math. Appl. (1998), Springer), 373 pages · Zbl 1014.68091 |
| [8] | Durand, A.; Grandjean, E., First-order queries on structures of bounded degree are computable with constant delay, ACM Trans. Comput. Log., 8, 4 (2007) · Zbl 1367.68086 |
| [9] | Ebbinghaus, H.-D.; Flum, J., Finite Model Theory (1995), Springer-Verlag · Zbl 0841.03014 |
| [10] | Elgot, C. C., Decision problem of finite automata design and related arithmetics, Trans. Am. Math. Soc., 98, 21-51 (1961) · Zbl 0111.01102 |
| [11] | Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (Karp, R. M., Complexity of Computation, SIAM-AMS Proceedings (1974)), 43-73 · Zbl 0303.68035 |
| [12] | Fagin, R., Monadic generalized spectra, Z. Math. Log. Grundl. Math., 21, 89-96 (1975) · Zbl 0317.02054 |
| [13] | Fagin, R., A spectrum hierarchy, Z. Math. Log. Grundl. Math., 21, 123-134 (1975) · Zbl 0311.02020 |
| [14] | Fagin, R., Finite-model theory—a personal perspective, Theor. Comput. Sci., 116, 1, 3-31 (1993) · Zbl 0788.03037 |
| [15] | Fagin, R.; Stockmeyer, L.; Vardi, M. Y., On monadic np vs. monadic co-np, Inf. Comput., 120, 1, 78-92 (July 1995) · Zbl 0835.68046 |
| [16] | (Flum, J.; Grädel, E.; Wilke, T., Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]. Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], Texts Log. Games, vol. 2 (2008), Amsterdam University Press) · Zbl 1198.03006 |
| [17] | Gaifman, H., On local and nonlocal properties, (Stern, J., Logic Colloquium’81 (1982), North Holland), 105-135 · Zbl 0518.03008 |
| [18] | Giammarresi, D., Computing languages by (bounded) local sets, (Ésik, Z.; Fülöp, Z., Developments in Language Theory. Developments in Language Theory, Lect. Notes Comput. Sci., vol. 2710 (2003), Springer), 304-315 · Zbl 1037.68084 |
| [19] | Giammarresi, D.; Restivo, A., Recognizable picture languages, Int. J. Pattern Recognit. Artif. Intell., 6, 2&3, 241-256 (1992) |
| [20] | Giammarresi, D.; Restivo, A., Two-dimensional finite state recognizability, Fundam. Inform., 25, 3, 399-422 (1996) · Zbl 0843.68054 |
| [21] | Giammarresi, D.; Restivo, A., Two-dimensional languages, (Handbook of Theoretical Computer Science. Handbook of Theoretical Computer Science, Beyond Words, vol. 3 (1997), Springer-Verlag: Springer-Verlag New York), 215-267, chapter 4 |
| [22] | Giammarresi, D.; Restivo, A.; Seibert, S.; Thomas, W., Monadic second-order logic over rectangular pictures and recognizability by tiling systems, Inf. Comput., 125, 1, 32-45 (1996) · Zbl 0853.68131 |
| [23] | Grädel, E., Capturing complexity classes by fragments of second order logic, (Proceedings of 6th IEEE Conference on Structure in Complexity Theory. Proceedings of 6th IEEE Conference on Structure in Complexity Theory, Chicago, 1991, 341-352. Proceedings of 6th IEEE Conference on Structure in Complexity Theory. Proceedings of 6th IEEE Conference on Structure in Complexity Theory, Chicago, 1991, 341-352, Theor. Comput. Sci., vol. 101 (1992)), 35-57, A preliminary version appeared · Zbl 0780.68040 |
| [24] | Grädel, E.; Kolaitis, Ph. G.; Libkin, L.; Marx, M.; Spencer, J.; Vardi, M. Y.; Venema, Y.; Weinstein, S., Finite Model Theory and Its Applications, Texts Theoret. Comput. Sci. (2007), Springer · Zbl 1133.03001 |
| [25] | Grädel, E.; Otto, M., On logics with two variables, Theor. Comput. Sci., 224, 1-2, 73-113 (1999) · Zbl 0948.03023 |
| [26] | Grandjean, E., First-order spectra with one variable, J. Comput. Syst. Sci., 40, 136-153 (1990) · Zbl 0694.68034 |
| [27] | Grandjean, E.; Olive, F., Graph properties checkable in linear time in the number of vertices, J. Comput. Syst. Sci., 68, 546-597 (2004) · Zbl 1069.68079 |
| [28] | Grandjean, E.; Olive, F., Descriptive complexity of picture languages, (Proc. Annual Conference of the EACSL. Proc. Annual Conference of the EACSL, CSL’12. Proc. Annual Conference of the EACSL. Proc. Annual Conference of the EACSL, CSL’12, Lect. Notes Comput. Sci. (2012)) |
| [29] | Grandjean, E.; Schwentick, T., Machine-independent characterizations and complete problems for deterministic linear time, SIAM J. Comput., 32, 1, 196-230 (2002) · Zbl 1029.68058 |
| [30] | Grohe, M.; Schwentick, T., Locality of order-invariant first-order formulas, ACM Trans. Comput. Log., 1, 1, 112-130 (2000) · Zbl 1365.68204 |
| [31] | Hanf, W., Model-theoretic methods in the study of elementary logic, (Addison, J.; Henkin, L.; Tarski, A., The Theory of Models (1965), North Holland), 132-145 · Zbl 0166.25801 |
| [32] | Hella, L.; Libkin, L.; Nurmonen, J., Notions of locality and their logical characterizations over finite models, J. Symb. Log., 64, 4, 1751-1773 (1999) · Zbl 0946.03012 |
| [33] | Immerman, N., Descriptive Complexity, Grad. Texts Comput. Sci. (1999), Springer · Zbl 0918.68031 |
| [34] | Iwamoto, C.; Yoneda, H.; Morita, K.; Imai, K., A time hierarchy theorem for nondeterministic cellular automata, (yi Cai, Jin; Barry Cooper, S.; Zhu, Hong, TAMC. TAMC, Lect. Notes Comput. Sci., vol. 4484 (2007), Springer), 511-520 · Zbl 1198.68174 |
| [35] | Jeandel, E.; Theyssier, G., Subshifts, languages and logic, (Volker, Diekert; Nowotka, Dirk, Developments in Language Theory, Proceedings of the 13th International Conference. Developments in Language Theory, Proceedings of the 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Developments in Language Theory, Proceedings of the 13th International Conference. Developments in Language Theory, Proceedings of the 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009, Lect. Notes Comput. Sci., vol. 5583 (2009), Springer), 288-299 · Zbl 1247.03068 |
| [36] | Kahr, A. S.; Moore, E. F.; Wang, H., Entscheidungsproblem reduced to the forall-exists-forall case, (Proc. Nat. Acad. Sci. U.S.A., vol. 48 (1962)), 365-377 · Zbl 0102.00801 |
| [37] | Kari, J., Basic concepts of cellular automata, (Rozenberg, G.; etal., Handbook of Natural Computing, vol. 1 (2012)), 3-24, see [60] |
| [38] | Kopczynski, E.; Tan, T., Regular graphs and the spectra of two-variable logic with counting, SIAM J. Comput., 44, 3, 786-818 (2015) · Zbl 1354.03039 |
| [39] | Kutrib, M., Nondeterministic cellular automata and languages, Int. J. Gen. Syst., 41, 6, 555-568 (2012) · Zbl 1277.68153 |
| [40] | Latteux, M.; Simplot, D., Recognizable picture languages and domino tiling (1994), Laboratoire d’Informatique Fondamentale de Lille, Université de Lille: Laboratoire d’Informatique Fondamentale de Lille, Université de Lille France, Internal Report IT-94-264 · Zbl 0912.68106 |
| [41] | Latteux, M.; Simplot, D., Context-sensitive string languages and recognizable picture languages, Inf. Comput., 138, 2, 160-169 (1997) · Zbl 0895.68083 |
| [42] | Latteux, M.; Simplot, D., Recognizable picture languages and domino tiling, Theor. Comput. Sci., 178, 1-2, 275-283 (1997) · Zbl 0912.68106 |
| [43] | Lautemann, C.; Schweikardt, N.; Schwentick, T., A logical characterisation of linear time on nondeterministic Turing machines, (Proc. 14th Symposium on Theoretical Aspect of Computer Science. Proc. 14th Symposium on Theoretical Aspect of Computer Science, STACS’99 (1999)), 143-152 · Zbl 0924.03070 |
| [44] | Libkin, L., Logics with counting and local properties, ACM Trans. Comput. Log., 1, 1, 33-59 (2000) · Zbl 1365.03025 |
| [45] | Libkin, L., Logics capturing local properties, ACM Trans. Comput. Log., 2, 1, 135-153 (2001) · Zbl 1365.03026 |
| [46] | Libkin, L., Elements of Finite Model Theory (2004), Springer · Zbl 1060.03002 |
| [47] | Lindell, S., A normal form for first-order logic over doubly-linked data structures, Int. J. Found. Comput. Sci., 19, 1, 205-217 (2008) · Zbl 1161.68401 |
| [48] | Lindgren, K.; Moore, C.; Nordahl, M., Complexity of two-dimensional patterns, J. Stat. Phys., 91, 5-6, 909-951 (1998) · Zbl 0917.68156 |
| [49] | Matz, O., One quantifier will do in existential monadic second-order logic over pictures, (MFCS (1998)), 751-759 · Zbl 0912.03004 |
| [50] | Matz, O.; Schweikardt, N., Expressive power of monadic logics on words, trees, pictures, and graphs, (Flum, J.; etal., Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas] (2008)), 531-552, see [16] · Zbl 1244.03118 |
| [51] | Matz, O.; Schweikardt, N.; Thomas, W., The monadic quantifier alternation hierarchy over grids and graphs, Inf. Comput., 179, 2, 356-383 (2002) · Zbl 1096.03007 |
| [52] | Matz, O.; Thomas, W., The monadic quantifier alternation hierarchy over graphs is infinite, (LICS (1997)), 236-244 |
| [53] | McNaughton, R.; Papert, S., Counter-Free Automata (1971), M.I.T. Press: M.I.T. Press Cambridge, Mass · Zbl 0232.94024 |
| [54] | Mortimer, M., On languages with two variables, Z. Math. Log. Grundl. Math., 21, 135 (1975) · Zbl 0343.02009 |
| [55] | Otto, M., A note on the number of monadic quantifiers in monadic \(\Sigma_1^1\), Inf. Process. Lett., 53, 6, 337-339 (1995) · Zbl 0875.68673 |
| [56] | Ozhigov, Y., Computations on nondeterministic cellular automata, Inf. Comput., 148, 2, 181-201 (1999) · Zbl 0924.68146 |
| [57] | Poupet, V., Cellular automata: real-time equivalence between one-dimensional neighborhoods, (STACS (2005)), 133-144 · Zbl 1118.68565 |
| [58] | Reinhardt, K., On some recognizable picture-languages, (MFCS (1998)), 760-770 |
| [59] | Reinhardt, K., The \(\# a = \# b\) pictures are recognizable, (STACS (2001)), 527-538 · Zbl 0976.03044 |
| [60] | (Rozenberg, G.; Bäck, T.; Kok, J. N., Handbook of Natural Computing (2012), Springer) · Zbl 1248.68001 |
| [61] | Schönhage, A., Storage modification machines, SIAM J. Comput., 9, 3, 490-508 (1980) · Zbl 0454.68034 |
| [62] | Schweikardt, N., The monadic quantifier alternation hierarchy over grids and pictures, (CSL (1997)), 441-460 · Zbl 0909.03009 |
| [63] | Schwentick, T., On winning ehrenfeucht games and monadic np, Ann. Pure Appl. Logic, 79, 1, 61-92 (1996) · Zbl 0856.03027 |
| [64] | Schwentick, T.; Barthelmann, K., Local normal forms for first-order logic with applications to games and automata, (Morvan, M.; Meinel, C.; Krob, D., STACS. STACS, Lect. Notes Comput. Sci., vol. 1373 (1998), Springer), 444-454 · Zbl 0892.03002 |
| [65] | Seese, D., Linear time computable problems and logical descriptions, Electron. Notes Theor. Comput. Sci., 2, 246-259 (1995) · Zbl 0910.68033 |
| [66] | Seese, D., Linear time computable problems and first-order descriptions, Math. Struct. Comput. Sci., 6, 505-526 (1996) · Zbl 0862.68056 |
| [67] | Seiferas, J. I.; Fischer, M. J.; Meyer, A. R., Separating nondeterministic time complexity classes, J. ACM, 25, 1, 146-167 (1978) · Zbl 0366.68038 |
| [68] | Sommerhalder, R.; van Westrhenen, S. C., Parallel language recognition in constant time by cellular automata, Acta Inform., 19, 397-407 (1983) · Zbl 0492.68061 |
| [69] | Terrier, V., Language recognition by cellular automata, (Rozenberg, G.; etal., Handbook of Natural Computing, vol. 1 (2012)), 123-158, see [60] |
| [70] | Thatcher, J. W.; Wright, J. B., Generalized finite automata theory with an application to a decision problem of Second-Order logic, Math. Syst. Theory, 2, 1, 57-81 (March 1968) · Zbl 0157.02201 |
| [71] | Thomas, W., Classifying regular events in symbolic logic, J. Comput. Syst. Sci., 25, 3, 360-376 (1982) · Zbl 0503.68055 |
| [72] | Thomas, W., On logics, tilings, and automata, (Albert, J. L.; Monien, B.; Rodríguez-Artalejo, M., ICALP. ICALP, Lect. Notes Comput. Sci., vol. 510 (1991), Springer), 441-454 · Zbl 0769.68100 |
| [73] | Trakhtenbrot, B. A., Finite automata and the logic of one-place predicates, Sib. Math. J., 3, 103-131 (1962), English translation in: AMS Transl. 59 (1966) 23-55 · Zbl 0115.00701 |
| [74] | van Emde Boas, P., Dominos are forever, (Proc. 1st GTI Workshop. Proc. 1st GTI Workshop, UGH, Paderborn (1982)), 75-95 |
| [75] | van Emde Boas, P., The convenience of tilings, (Complexity, Logic and Recursion Theory. Complexity, Logic and Recursion Theory, Lect. Notes Pure Appl. Math., vol. 187 (1997)), 331-363 · Zbl 0874.03050 |
| [76] | Wang, H., Dominoes and the AEA case of the decision problem, (Proceedings of the Symposium on the Mathematical Theory of Automata. Proceedings of the Symposium on the Mathematical Theory of Automata, April 1962 (1963), Polytechnic Press: Polytechnic Press New York, Brooklyn), 23-55 · Zbl 0137.01001 |
| [77] | Wang, H., Computation, Logic, Philosophy. A Collection of Essays (1990), Science Press: Science Press Beijing, Kluwer Academic Publishers, Dordrecht · Zbl 0899.01037 |
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.
