Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-28T11:58:18.407Z Has data issue: false hasContentIssue false
  • English
  • Français

Regular languages definable by Lindström quantifiers

Published online by Cambridge University Press:  15 November 2003

Zoltán Ésik  and
Kim G. Larsen
Zoltán Ésik
Affiliation:
Dept. of Computer Science, University of Szeged, POB 652, 6701 Szeged, Hungary; [email protected].
Kim G. Larsen
Affiliation:
Dept. of Computer Science, Aalborg University, Fredrik Bajers Vej 7E, 9220 Aalborg, Denmark; [email protected].
Get access

Abstract

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.

Keywords

Regular languagelogicLindström quantifierexpressive powersemidirect product.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 37 , Issue 3 , July 2003 , pp. 179 - 241
Copyright
© EDP Sciences, 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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).
Barrington, D.A.M., Compton, K., Straubing, H. and Therien, D., Regular languages in NC1. J. Comput. System Sci. 44 (1992) 478-499. CrossRef
Barrington, D., Immerman, N. and Straubing, H.: On uniformity within NC1 . J. Comput. System Sci. 41 (1990) 274-306. CrossRef
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.
D. Beauquier and A. Rabinovitch, Monadic logic of order over naturals has no finite base. J. Logic and Comput. (to appear).
Büchi, J.R., Weak second order logic and finite automata. Zeit. Math. Logik Grund. Math. 6 (1960) 66-92. CrossRef
Burtschick, H.-J. and Vollmer, H., Lindström quantifiers and leaf language definability. Int. J. Found. Comput. Sci. 9 (1998) 277-294. CrossRef
Cohen, J., Perrin, D. and Pin, J.-E., On the expressive power of temporal logic. J. Comput. System Sci. 46 (1993) 271-294. CrossRef
Dömösi, P. and Ésik, Z., Critical classes for the α0 -product. Theoret. Comput. Sci. 61 (1988) 17-24. CrossRef
H.-J. Ebbinghaus and J. Flum, Finite Model Theory. 2nd ed., Springer (1999).
S. Eilenberg, Automata, Languages, and Machines. vol. A and B, Academic Press (1974, 1976).
Elgot, C., Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98 (1961) 21-51. CrossRef
Ésik, Z., Results on homomorphic realization of automata by α0 -products. Theoret. Comput. Sci. 87 (1991) 229-249. CrossRef
Ésik, Z. and Ito, M., Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybernet. 16 (2003) 1-28.
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.
N. Immerman, Descriptive Complexity. Graduate Texts in Computer Science, Springer-Verlag, New York (1999).
Krohn, K. and Rhodes, J., Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc. 116 (1965) 450-464. CrossRef
Lautemann, C., McKenzie, P. and Schwentick, Th., The descriptive complexity approach to LOGCFL. J. Comput. System Sci. 62 (2001) 629-652. CrossRef
Lindström, P., First order predicate logic with generalized quantifiers. Theoria 32 (1966) 186-195.
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.
Maurer, W.D. and Rhodes, J.L., A property of finite simple non-abelian groups, Proc. Amer. Math. Soc. 16 (1965) 552-554. CrossRef
R. McNaughton and S. Papert, Counter-Free Automata. MIT Press (1971).
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.
J.-E. Pin, Varieties of Formal Languages. Plenum (1986).
Pin, J.-E., Logic, semigroups and automata on words, Ann. Math. Artif. Intell. 16 (1996) 343-384. CrossRef
A. Pnueli, The temporal logic of programs, in: 18th IEEE Symp. Foundations of Computer Science, Providence (1977) 46-57.
Rhodes, J., Undecidability, automata, and pseudo-varieties of finite semigroups, Int. J. Algebra and Comput. 9 (1999) 455-473. CrossRef
Rhodes, J. and Tilson, B., The kernel of monoid morphisms, J. Pure Appl. Algebra 62 (1989) 227-268. CrossRef
Schützenberger, M.P., On finite monoids having only trivial subgroup. Inf. and Control 8 (1965) 190-194. CrossRef
Straubing, H., Families of recognizable sets corresponding to certain varieties of finite monoids. J. Pure Appl. Algebra 15 (1979) 305-318. CrossRef
H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser (1994).
H. Straubing, On logical descriptions of regular languages, in: LATIN 2002, LNCS 2286, Springer (2002) 528-538.
H. Straubing and D. Therien, Regular languages defined with a bounded number of variables, in: STACS 2001, LNCS 2010, Springer (2001) 555-562.
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.
Straubing, H., Therien, D. and Thomas, W., Regular languages defined with generalized quantifiers. Inf. and Comput. 118 (1995) 289-301. CrossRef
Therien, D., Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. CrossRef
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.
W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science. Vol. B, Elsevier, Amsterdam (1990) 133-191.
W. Thomas, Languages, automata, and logic, in: Handbook of Formal Languages. Vol. 3, Springer (1997) 389-455.
Trakhtenbrot, B.A., Finite automata and logic of monadic predicates, Dokl. Akad. Nauk SSSR 140 (1961) 326-329.
J. Väänänen (ed.), Generalized Quantifiers and Computation, LNCS 1754, Springer (1997).