Regular languages definable by Lindström quantifiers

Zoltán Ésik; Kim G. Larsen

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 37, Issue: 3, page 179-241
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Ésik, Zoltán, and Larsen, Kim G.. "Regular languages definable by Lindström quantifiers." RAIRO - Theoretical Informatics and Applications 37.3 (2010): 179-241. <http://eudml.org/doc/92721>.

@article{Ésik2010,
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. },
author = {Ésik, Zoltán, Larsen, Kim G.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Regular language; logic; Lindström quantifier; expressive power; semidirect product.; regular languages; Lindström quantifiers; expressive powers; semidirect products},
language = {eng},
month = {3},
number = {3},
pages = {179-241},
publisher = {EDP Sciences},
title = {Regular languages definable by Lindström quantifiers},
url = {http://eudml.org/doc/92721},
volume = {37},
year = {2010},
}

TY - JOUR
AU - Ésik, Zoltán
AU - Larsen, Kim G.
TI - Regular languages definable by Lindström quantifiers
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 3
SP - 179
EP - 241
AB - 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.
LA - eng
KW - Regular language; logic; Lindström quantifier; expressive power; semidirect product.; regular languages; Lindström quantifiers; expressive powers; semidirect products
UR - http://eudml.org/doc/92721
ER -

References

top
  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).  
  2. D.A.M. Barrington, K. Compton, H. Straubing and D. Therien, Regular languages in NC1. J. Comput. System Sci.44 (1992) 478-499.  
  3. D. Barrington, N. Immerman and H. Straubing: On uniformity within NC1. J. Comput. System Sci.41 (1990) 274-306.  
  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).  
  6. J.R. Büchi, Weak second order logic and finite automata. Zeit. Math. Logik Grund. Math.6 (1960) 66-92.  
  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.  
  9. P. Dömösi and Z. Ésik, Critical classes for the α0-product. Theoret. Comput. Sci.61 (1988) 17-24.  
  10. H.-J. Ebbinghaus and J. Flum, Finite Model Theory. 2nd ed., Springer (1999).  
  11. S. Eilenberg, Automata, Languages, and Machines. vol. A and B, Academic Press (1974, 1976).  
  12. C. Elgot, Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc.98 (1961) 21-51.  
  13. Z. Ésik, Results on homomorphic realization of automata by α0-products. Theoret. Comput. Sci.87 (1991) 229-249.  
  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.  
  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.  
  16. N. Immerman, Descriptive Complexity. Graduate Texts in Computer Science, Springer-Verlag, New York (1999).  
  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.  
  18. C. Lautemann, P. McKenzie and Th. Schwentick, The descriptive complexity approach to LOGCFL. J. Comput. System Sci.62 (2001) 629-652.  
  19. P. Lindström, First order predicate logic with generalized quantifiers. Theoria32 (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.  
  21. W.D. Maurer and J.L. Rhodes, A property of finite simple non-abelian groups, Proc. Amer. Math. Soc.16 (1965) 552-554.  
  22. R. McNaughton and S. Papert, Counter-Free Automata. MIT Press (1971).  
  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.  
  24. J.-E. Pin, Varieties of Formal Languages. Plenum (1986).  
  25. J.-E. Pin, Logic, semigroups and automata on words, Ann. Math. Artif. Intell.16 (1996) 343-384.  
  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.  
  28. J. Rhodes and B. Tilson, The kernel of monoid morphisms, J. Pure Appl. Algebra62 (1989) 227-268.  
  29. M.P. Schützenberger, On finite monoids having only trivial subgroup. Inf. and Control8 (1965) 190-194.  
  30. H. Straubing, Families of recognizable sets corresponding to certain varieties of finite monoids. J. Pure Appl. Algebra15 (1979) 305-318.  
  31. H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser (1994).  
  32. H. Straubing, On logical descriptions of regular languages, in: LATIN 2002, LNCS 2286, Springer (2002) 528-538.  
  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.  
  35. H. Straubing, D. Therien and W. Thomas, Regular languages defined with generalized quantifiers. Inf. and Comput.118 (1995) 289-301.  
  36. D. Therien, Classification of finite monoids: The language approach. Theoret. Comput. Sci.14 (1981) 195-208.  
  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.  
  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 SSSR140 (1961) 326-329.  
  41. J. Väänänen (ed.), Generalized Quantifiers and Computation, LNCS 1754, Springer (1997).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.