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).  Zbl0181.01501
  2. D.A.M. Barrington, K. Compton, H. Straubing and D. Therien, Regular languages in NC1. J. Comput. System Sci.44 (1992) 478-499.  Zbl0757.68057
  3. D. Barrington, N. Immerman and H. Straubing: On uniformity within NC1. J. Comput. System Sci.41 (1990) 274-306.  Zbl0719.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).  Zbl1056.03007
  6. J.R. Büchi, Weak second order logic and finite automata. Zeit. Math. Logik Grund. Math.6 (1960) 66-92.  Zbl0103.24705
  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. 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. P. Dömösi and Z. Ésik, Critical classes for the α0-product. Theoret. Comput. Sci.61 (1988) 17-24.  Zbl0693.68033
  10. H.-J. Ebbinghaus and J. Flum, Finite Model Theory. 2nd ed., Springer (1999).  Zbl0932.03032
  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.  Zbl0111.01102
  13. Z. Ésik, Results on homomorphic realization of automata by α0-products. Theoret. Comput. Sci.87 (1991) 229-249.  Zbl0744.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.  Zbl1027.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.  Zbl0999.03033
  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.  Zbl0148.01002
  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. P. Lindström, First order predicate logic with generalized quantifiers. Theoria32 (1966) 186-195.  Zbl1230.03072
  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. 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. 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.  Zbl0943.68119
  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.  Zbl1027.20038
  28. J. Rhodes and B. Tilson, The kernel of monoid morphisms, J. Pure Appl. Algebra62 (1989) 227-268.  Zbl0698.20056
  29. M.P. Schützenberger, On finite monoids having only trivial subgroup. Inf. and Control8 (1965) 190-194.  Zbl0131.02001
  30. H. Straubing, Families of recognizable sets corresponding to certain varieties of finite monoids. J. Pure Appl. Algebra15 (1979) 305-318.  Zbl0414.20056
  31. H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser (1994).  Zbl0816.68086
  32. H. Straubing, On logical descriptions of regular languages, in: LATIN 2002, LNCS 2286, Springer (2002) 528-538.  Zbl1059.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.  Zbl0976.68092
  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. H. Straubing, D. Therien and W. Thomas, Regular languages defined with generalized quantifiers. Inf. and Comput.118 (1995) 289-301.  Zbl0826.68072
  36. D. Therien, Classification of finite monoids: The language approach. Theoret. Comput. Sci.14 (1981) 195-208.  Zbl0471.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.  Zbl0900.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 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.