×

Uniform and nonuniform recognizability. (English) Zbl 1064.68059

Summary: Deterministic and nondeterministic finite-state recognizability over finite structures are introduced in an algebraic setting, avoiding detailed computational conventions as needed in the definition of finite-state acceptors. For deterministic recognizability, the classical approach is adopted, using a “uniform” homomorphism from the input domain (consisting of terms) into a finite algebra. For the nondeterministic case, we refer to relational input structures and to an acceptance via relational homomorphisms (which are applied “nonuniformly” since they depend on the input structures). We show how this approach encompasses known models of nondeterministic automata over finite words, trees, pictures, and graphs, and present some elementary metaresults connecting uniform recognizability, nonuniform recognizability, and monadic second-order logic.

MSC:

68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
03D05 Automata and formal grammars in connection with logical questions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berstel, J., Transductions and Context-Free Languages (1979), Teubner-Verlag: Teubner-Verlag Stuttgart · Zbl 0424.68040
[2] Büchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Logik Grundl. Math., 6, 66-92 (1960) · Zbl 0103.24705
[3] Büchi, J. R., Finite Automata, Their Algebras and Grammars (1989), Springer: Springer New York · Zbl 0715.68062
[4] Courcelle, B., On recognizable sets and tree automata, (Nivat, M.; Ait-Kaci, H., Resolution of Equations in Algebraic Structures, Vol. I (1989), Academic Press: Academic Press New York), 93-126
[5] Courcelle, B., The monadic second-order logic on graphs I, Recognizable sets of finite graphs, Inform. Comput., 85, 12-75 (1990) · Zbl 0722.03008
[6] Courcelle, B., Graph-rewritingan algebraic and logic approach, (Leeuwen, J.v., Handbook of Theoretical Computer Science, Vol. B (1990), Elsevier: Elsevier Amsterdam), 193-240
[7] Courcelle, B., The monadic second-order logic of graphs V: on closing the gap between recognizability and recognizability, Theoret. Comput. Sci., 80, 153-202 (1991) · Zbl 0754.68065
[8] Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic, (Rozenberg, G., Handbook of Graph Transformations, Vol. I: Foundations (1996), World Scienfific: World Scienfific Singapore) · Zbl 0945.68144
[9] Doner, J., Tree acceptors and some of their applications, J. Comput. System Sci., 4, 406-451 (1970) · Zbl 0212.02901
[10] Diekert, V.; Rozenberg, G., The Book of Traces (1995), World Scientific: World Scientific Singapore
[11] Eilenberg, S., Automata, Languages, and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[12] Elgot, C. C., Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc., 98, 21-52 (1961) · Zbl 0111.01102
[13] T. Feder, M.Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, Proc. ACM Symp. on the Theory of Computing, ACM 1993.; T. Feder, M.Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, Proc. ACM Symp. on the Theory of Computing, ACM 1993. · Zbl 0914.68075
[14] Giammarresi, D.; Restivo, A., Two-dimensional languages, (Rozenberg, G.; Salomaa, A., Handbook of Formal Language Theory, Vol. 3 (1997), Springer: Springer New York), 215-268
[15] Giammarresi, D.; Restivo, A.; Seibert, S.; Thomas, W., Monadic second-order logic over rectangular pictures and recognizability by tiling systems, Inform. Comput., 125, 32-45 (1996) · Zbl 0853.68131
[16] Gécseg, F.; Steinby, M., Tree Automata (1984), Akadémiai: Akadémiai Kiodó, Budapest
[17] Gécseg, F.; Steinby, M., Tree languages, (Rozenberg, G.; Salomaa, A., Handbook of Formal Language Theory, Vol. 3 (1997), Springer: Springer New York), 1-68 · Zbl 0396.68041
[18] Lapoire, D., Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width, (Proc. STACS98. Proc. STACS98, Lecture Notes in Computer Science, Vol. 1373 (1998), Springer: Springer Berlin), 618-628 · Zbl 0936.03036
[19] Thomas, W., On logics, tilings, and automata, (Leach, J.; etal., Automata, Languages, and Programming. Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 510 (1991), Springer: Springer Berlin-Heidelberg-New York), 441-453 · Zbl 0769.68100
[20] Thomas, W., Languages, automata, and logic, (Rozenberg, G.; Salomaa, A., Handbook of Formal Language Theory, Vol. 3 (1997), Springer: Springer New York), 389-456
[21] Thatcher, J. W.; Wright, J. B., Generalized finite automata with an application to a decision problem of second order logic, Math. Systems Theory, 2, 57-82 (1968) · Zbl 0157.02201
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.