Regular languages definable by Lindström quantifiers
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 3, pp. 179-241.

In our main result, we establish a formal connection between Lindström quantifiers with respect to regular languages and the double semidirect product of finite monoids with a distinguished set of generators. We use this correspondence to characterize the expressive power of Lindström quantifiers associated with a class of regular languages.

DOI : https://doi.org/10.1051/ita:2003017
Classification : 20M35,  68Q45,  68Q60,  68Q70
Mots clés : regular language, logic, Lindström quantifier, expressive power, semidirect product
@article{ITA_2003__37_3_179_0,
     author = {\'Esik, Zolt\'an and Larsen, Kim G.},
     title = {Regular languages definable by {Lindstr\"om} quantifiers},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {179--241},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {3},
     year = {2003},
     doi = {10.1051/ita:2003017},
     zbl = {1046.20042},
     mrnumber = {2021315},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2003017/}
}
TY  - JOUR
AU  - Ésik, Zoltán
AU  - Larsen, Kim G.
TI  - Regular languages definable by Lindström quantifiers
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2003
DA  - 2003///
SP  - 179
EP  - 241
VL  - 37
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2003017/
UR  - https://zbmath.org/?q=an%3A1046.20042
UR  - https://www.ams.org/mathscinet-getitem?mr=2021315
UR  - https://doi.org/10.1051/ita:2003017
DO  - 10.1051/ita:2003017
LA  - en
ID  - ITA_2003__37_3_179_0
ER  - 
Ésik, Zoltán; Larsen, Kim G. Regular languages definable by Lindström quantifiers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 3, pp. 179-241. doi : 10.1051/ita:2003017. http://www.numdam.org/articles/10.1051/ita:2003017/

[1] M.A. Arbib (ed.), Algebraic Theory of Machines, Languages, and Semigroups. With a major contribution by K. Krohn and J.L. Rhodes, Academic Press (1968). | MR 232875 | Zbl 0181.01501

[2] D.A.M. Barrington, K. Compton, H. Straubing and D. Therien, Regular languages in NC 1 . J. Comput. System Sci. 44 (1992) 478-499. | Zbl 0757.68057

[3] D. Barrington, N. Immerman and H. Straubing: On uniformity within 𝑁𝐶 1 . J. Comput. System Sci. 41 (1990) 274-306. | Zbl 0719.68023

[4] A. Baziramwabo, P. Mckenzie and D. Therien, Modular temporal logic, in: 14th Annual IEEE Symposium on Logic in Computer Science, Trento (1999). IEEE Computer Society, 344-351.

[5] D. Beauquier and A. Rabinovitch, Monadic logic of order over naturals has no finite base. J. Logic and Comput. (to appear). | MR 1900379 | Zbl 1056.03007

[6] J.R. Büchi, Weak second order logic and finite automata. Zeit. Math. Logik Grund. Math. 6 (1960) 66-92. | Zbl 0103.24705

[7] H.-J. Burtschick and H. Vollmer, Lindström quantifiers and leaf language definability. Int. J. Found. Comput. Sci. 9 (1998) 277-294.

[8] J. Cohen, D. Perrin and J.-E. Pin, On the expressive power of temporal logic. J. Comput. System Sci. 46 (1993) 271-294. | Zbl 0784.03014

[9] P. Dömösi and Z. Ésik, Critical classes for the α 0 -product. Theoret. Comput. Sci. 61 (1988) 17-24. | Zbl 0693.68033

[10] H.-J. Ebbinghaus and J. Flum, Finite Model Theory. 2nd ed., Springer (1999). | MR 1716820 | Zbl 0932.03032

[11] S. Eilenberg, Automata, Languages, and Machines. vol. A and B, Academic Press (1974, 1976). | MR 530382 | Zbl 0317.94045

[12] C. Elgot, Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98 (1961) 21-51. | Zbl 0111.01102

[13] Z. Ésik, Results on homomorphic realization of automata by α 0 -products. Theoret. Comput. Sci. 87 (1991) 229-249. | Zbl 0744.68104

[14] Z. Ésik and M. Ito, Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybernet. 16 (2003) 1-28. | Zbl 1027.68074

[15] M. Galota and H. Vollmer, A generalization of the Büchi-Elgot-Trakhtenbrot theorem, in: Computer Science Logic, 15th International Workshop, CSL (2001), Paris (2001), LNCS 2142, Springer, 355-368. | Zbl 0999.03033

[16] N. Immerman, Descriptive Complexity. Graduate Texts in Computer Science, Springer-Verlag, New York (1999). | MR 1732784 | Zbl 0918.68031

[17] K. Krohn and J. Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc. 116 (1965) 450-464. | Zbl 0148.01002

[18] C. Lautemann, P. Mckenzie and Th. Schwentick, The descriptive complexity approach to LOGCFL. J. Comput. System Sci. 62 (2001) 629-652. | Zbl 0983.68108

[19] P. Lindström, First order predicate logic with generalized quantifiers. Theoria 32 (1966) 186-195.

[20] P. Mckenzie, Th. Schwentick, D. Therien and H. Vollmer, The many faces of a translation, in: Automata, Languages and Programming, 27th International Colloquium, ICALP'00, LNCS 1853, 890-901. | Zbl 0973.68155

[21] W.D. Maurer and J.L. Rhodes, A property of finite simple non-abelian groups, Proc. Amer. Math. Soc. 16 (1965) 552-554. | Zbl 0132.26903

[22] R. Mcnaughton and S. Papert, Counter-Free Automata. MIT Press (1971). | MR 371538 | Zbl 0232.94024

[23] T. Peichl and H. Vollmer, Finite automata with generalized acceptance criteria, in: Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, LNCS 1644, Springer, 605-614. | Zbl 0943.68119

[24] J.-E. Pin, Varieties of Formal Languages. Plenum (1986). | MR 912694 | Zbl 0632.68069

[25] J.-E. Pin, Logic, semigroups and automata on words, Ann. Math. Artif. Intell. 16 (1996) 343-384. | Zbl 0860.68071

[26] A. Pnueli, The temporal logic of programs, in: 18th IEEE Symp. Foundations of Computer Science, Providence (1977) 46-57.

[27] J. Rhodes, Undecidability, automata, and pseudo-varieties of finite semigroups, Int. J. Algebra and Comput. 9 (1999) 455-473. | Zbl 1027.20038

[28] J. Rhodes and B. Tilson, The kernel of monoid morphisms, J. Pure Appl. Algebra 62 (1989) 227-268. | Zbl 0698.20056

[29] M.P. Schützenberger, On finite monoids having only trivial subgroup. Inf. and Control 8 (1965) 190-194. | Zbl 0131.02001

[30] H. Straubing, Families of recognizable sets corresponding to certain varieties of finite monoids. J. Pure Appl. Algebra 15 (1979) 305-318. | Zbl 0414.20056

[31] H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser (1994). | MR 1269544 | Zbl 0816.68086

[32] H. Straubing, On logical descriptions of regular languages, in: LATIN 2002, LNCS 2286, Springer (2002) 528-538. | Zbl 1059.03034

[33] H. Straubing and D. Therien, Regular languages defined with a bounded number of variables, in: STACS 2001, LNCS 2010, Springer (2001) 555-562.

[34] H. Straubing, D. Therien and W. Thomas, Regular languages defined with generalized quantifiers, Automata, languages and programming (Tampere, 1988), Lecture Notes in Comput. Sci. 317, Springer, Berlin (1988) 561-575. | Zbl 0658.68098

[35] H. Straubing, D. Therien and W. Thomas, Regular languages defined with generalized quantifiers. Inf. and Comput. 118 (1995) 289-301. | Zbl 0826.68072

[36] D. Therien, Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. | Zbl 0471.20055

[37] D. Therien and Th. Wilke, Temporal logic and semidirect products: An effective characterization of the until hierarchy, in: 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington. IEEE Computer Society (1996) 256-263.

[38] W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science. Vol. B, Elsevier, Amsterdam (1990) 133-191. | Zbl 0900.68316

[39] W. Thomas, Languages, automata, and logic, in: Handbook of Formal Languages. Vol. 3, Springer (1997) 389-455.

[40] B.A. Trakhtenbrot, Finite automata and logic of monadic predicates, Dokl. Akad. Nauk SSSR 140 (1961) 326-329. | Zbl 0115.00702

[41] J. Väänänen (ed.), Generalized Quantifiers and Computation, LNCS 1754, Springer (1997). | MR 1773122

Cité par Sources :