Regular languages definable by Lindström quantifiers

 Access to full text

 Full (PDF)

1. [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). Zbl0181.01501MR232875
2. [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. Zbl0757.68057
3. [3] D. Barrington, N. Immerman and H. Straubing: On uniformity within ${\mathrm{𝑁𝐶}}^1$. J. Comput. System Sci. 41 (1990) 274–306. Zbl0719.68023
4. [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. [5] D. Beauquier and A. Rabinovitch, Monadic logic of order over naturals has no finite base. J. Logic and Comput. (to appear). Zbl1056.03007MR1900379
6. [6] J.R. Büchi, Weak second order logic and finite automata. Zeit. Math. Logik Grund. Math. 6 (1960) 66–92. Zbl0103.24705
7. [7] H.-J. Burtschick and H. Vollmer, Lindström quantifiers and leaf language definability. Int. J. Found. Comput. Sci. 9 (1998) 277–294. Zbl1319.68104
8. [8] J. Cohen, D. Perrin and J.-E. Pin, On the expressive power of temporal logic. J. Comput. System Sci. 46 (1993) 271–294. Zbl0784.03014
9. [9] P. Dömösi and Z. Ésik, Critical classes for the ${\alpha }_0$-product. Theoret. Comput. Sci. 61 (1988) 17–24. Zbl0693.68033
10. [10] H.-J. Ebbinghaus and J. Flum, Finite Model Theory. 2nd ed., Springer (1999). Zbl0932.03032MR1716820
11. [11] S. Eilenberg, Automata, Languages, and Machines. vol. A and B, Academic Press (1974, 1976). Zbl0317.94045MR530382
12. [12] C. Elgot, Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98 (1961) 21–51. Zbl0111.01102
13. [13] Z. Ésik, Results on homomorphic realization of automata by ${\alpha }_0$-products. Theoret. Comput. Sci. 87 (1991) 229–249. Zbl0744.68104
14. [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. Zbl1027.68074
15. [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. Zbl0999.03033
16. [16] N. Immerman, Descriptive Complexity. Graduate Texts in Computer Science, Springer-Verlag, New York (1999). Zbl0918.68031MR1732784
17. [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. Zbl0148.01002
18. [18] C. Lautemann, P. McKenzie and Th. Schwentick, The descriptive complexity approach to LOGCFL. J. Comput. System Sci. 62 (2001) 629–652. Zbl0983.68108
19. [19] P. Lindström, First order predicate logic with generalized quantifiers. Theoria 32 (1966) 186–195. Zbl1230.03072
20. [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. Zbl0973.68155
21. [21] W.D. Maurer and J.L. Rhodes, A property of finite simple non-abelian groups, Proc. Amer. Math. Soc. 16 (1965) 552–554. Zbl0132.26903
22. [22] R. McNaughton and S. Papert, Counter-Free Automata. MIT Press (1971). Zbl0232.94024MR371538
23. [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. Zbl0943.68119
24. [24] J.-E. Pin, Varieties of Formal Languages. Plenum (1986). Zbl0632.68069MR912694
25. [25] J.-E. Pin, Logic, semigroups and automata on words, Ann. Math. Artif. Intell. 16 (1996) 343–384. Zbl0860.68071
26. [26] A. Pnueli, The temporal logic of programs, in: 18th IEEE Symp. Foundations of Computer Science, Providence (1977) 46–57. 
27. [27] J. Rhodes, Undecidability, automata, and pseudo-varieties of finite semigroups, Int. J. Algebra and Comput. 9 (1999) 455–473. Zbl1027.20038
28. [28] J. Rhodes and B. Tilson, The kernel of monoid morphisms, J. Pure Appl. Algebra 62 (1989) 227–268. Zbl0698.20056
29. [29] M.P. Schützenberger, On finite monoids having only trivial subgroup. Inf. and Control 8 (1965) 190–194. Zbl0131.02001
30. [30] H. Straubing, Families of recognizable sets corresponding to certain varieties of finite monoids. J. Pure Appl. Algebra 15 (1979) 305–318. Zbl0414.20056
31. [31] H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser (1994). Zbl0816.68086MR1269544
32. [32] H. Straubing, On logical descriptions of regular languages, in: LATIN 2002, LNCS 2286, Springer (2002) 528–538. Zbl1059.03034
33. [33] H. Straubing and D. Therien, Regular languages defined with a bounded number of variables, in: STACS 2001, LNCS 2010, Springer (2001) 555–562. Zbl0976.68092
34. [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. Zbl0658.68098
35. [35] H. Straubing, D. Therien and W. Thomas, Regular languages defined with generalized quantifiers. Inf. and Comput. 118 (1995) 289–301. Zbl0826.68072
36. [36] D. Therien, Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195–208. Zbl0471.20055
37. [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. [38] W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science. Vol. B, Elsevier, Amsterdam (1990) 133–191. Zbl0900.68316
39. [39] W. Thomas, Languages, automata, and logic, in: Handbook of Formal Languages. Vol. 3, Springer (1997) 389–455. 
40. [40] B.A. Trakhtenbrot, Finite automata and logic of monadic predicates, Dokl. Akad. Nauk SSSR 140 (1961) 326–329. Zbl0115.00702
41. [41] J. Väänänen (ed.), Generalized Quantifiers and Computation, LNCS 1754, Springer (1997). MR1773122

1. Ondřej Klíma, Libor Polák, On Varieties of Literally Idempotent Languages