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 : 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},
     mrnumber = {2021315},
     zbl = {1046.20042},
     language = {en},
     url = {http://archive.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
SP  - 179
EP  - 241
VL  - 37
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2003017/
DO  - 10.1051/ita:2003017
LA  - en
ID  - ITA_2003__37_3_179_0
ER  - 
%0 Journal Article
%A Ésik, Zoltán
%A Larsen, Kim G.
%T Regular languages definable by Lindström quantifiers
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2003
%P 179-241
%V 37
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2003017/
%R 10.1051/ita:2003017
%G en
%F ITA_2003__37_3_179_0
É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://archive.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 | Zbl

[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

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

[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 | Zbl

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

[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

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

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

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

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

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

[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

[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

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

[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

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

[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

[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

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

[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

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

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

[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

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

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

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

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

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

[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

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

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

[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

[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

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

Cité par Sources :