Some results on 𝒞 -varieties

Jean-Éric Pin; Howard Straubing

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

  • Volume: 39, Issue: 1, page 239-262
  • ISSN: 0988-3754

Abstract

top
In an earlier paper, the second author generalized Eilenberg’s variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman’s theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form ( a 1 a 2 ⋯ a k ) + , where a 1 , ... , a k are distinct letters. Next, we generalize the notions of Mal’cev product, positive varieties, and polynomial closure. Our results not only extend those already known, but permit a unified approach of different cases that previously required separate treatment.

How to cite

top

Pin, Jean-Éric, and Straubing, Howard. "Some results on $\mathcal {C}$-varieties." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.1 (2005): 239-262. <http://eudml.org/doc/244768>.

@article{Pin2005,
abstract = {In an earlier paper, the second author generalized Eilenberg’s variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman’s theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form $(a_1a_2\cdots a_k)^+$, where $a_1,\ldots ,a_k$ are distinct letters. Next, we generalize the notions of Mal’cev product, positive varieties, and polynomial closure. Our results not only extend those already known, but permit a unified approach of different cases that previously required separate treatment.},
author = {Pin, Jean-Éric, Straubing, Howard},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {monoid morphisms; varieties; regular languages; finitely generated free monoids; length-preserving morphisms; finite monoids; stamps; identities},
language = {eng},
number = {1},
pages = {239-262},
publisher = {EDP-Sciences},
title = {Some results on $\mathcal \{C\}$-varieties},
url = {http://eudml.org/doc/244768},
volume = {39},
year = {2005},
}

TY - JOUR
AU - Pin, Jean-Éric
AU - Straubing, Howard
TI - Some results on $\mathcal {C}$-varieties
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 1
SP - 239
EP - 262
AB - In an earlier paper, the second author generalized Eilenberg’s variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman’s theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form $(a_1a_2\cdots a_k)^+$, where $a_1,\ldots ,a_k$ are distinct letters. Next, we generalize the notions of Mal’cev product, positive varieties, and polynomial closure. Our results not only extend those already known, but permit a unified approach of different cases that previously required separate treatment.
LA - eng
KW - monoid morphisms; varieties; regular languages; finitely generated free monoids; length-preserving morphisms; finite monoids; stamps; identities
UR - http://eudml.org/doc/244768
ER -

References

top
  1. [1] D.A.M. Barrington, K.J. Compton, H. Straubing and D. Thérien, Regular languages in n c 1 . J. Comput. Syst. Sci. 44 (1992) 478–499. Zbl0757.68057
  2. [2] M. Branco, Varieties of languages, in Semigroups, Algorithms, Automata and Languages, edited by G.M.S. Gomes, J.-É. Pin and P. Silva. World Scientific (2002) 91–132. Zbl1031.20052
  3. [3] S. Eilenberg, Automata, languages, and machines. Vol. B. Academic Press, Harcourt Brace Jovanovich Publishers, New York, (1976). With two chapters (“Depth decomposition theorem” and “Complexity of semigroups and morphisms”) by Bret Tilson. Pure Appl. Math. 59. Zbl0359.94067
  4. [4] S. Eilenberg and M.-P. Schützenberger, On pseudovarieties. Adv. Math. 19 (1976) 413–418. Zbl0351.20035
  5. [5] M. Kunc, Equational description of pseudovarieties of homomorphisms. Theor. Inform. Appl. 37 (2003) 243–254. Zbl1045.20049
  6. [6] D. Perrin and J.-É. Pin, Infinite Words. Pure and Applied Mathematics 141 2004. Zbl1094.68052
  7. [7] J.-É. Pin, A variety theorem without complementation. Russian Math. (Izvestija vuzov. Matematika) 39 (1995) 80–90. 
  8. [8] J.-É. Pin, Syntactic semigroups, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997) 679–746. 
  9. [9] J.-É. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci. 292 (2003) 317–342. Zbl1064.68057
  10. [10] J.-É. Pin, H. Straubing and D. Thérien, Some results on the generalized star-height problem. Inform. Comput. 101 (1992) 219–250. Zbl0769.68066
  11. [11] J.-É. Pin and P. Weil, Profinite semigroups, mal’cev products and identities. J. Algebra 182 (1996) 604–626. Zbl0857.20040
  12. [12] J.-É. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Syst. 30 (1997) 1–39. Zbl0872.68119
  13. [13] J.-É. Pin and P. Weil, Semidirect products of ordered semigroups. Commun. Algebra 30 (2002) 149–169. Zbl1003.06009
  14. [14] J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1–10. Zbl0484.08007
  15. [15] I. Simon, Hierarchies of Events with Dot-Depth One. Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, Canada (1972). 
  16. [16] I. Simon, Piecewise testable events, in Proc. 2nd GI Conf., edited by H. Brackage. Springer-Verlag, Berlin, Heidelberg, New York. Lect. Notes Comp. Sci. 33 (1975) 214–222. Zbl0316.68034
  17. [17] H. Straubing, Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA (1994). Zbl0816.68086MR1269544
  18. [18] H. Straubing, On logical descriptions of regular languages, in LATIN 2002. Springer, Berlin, Lect. Notes Comput. Sci. 2286 (2002) 528–538. Zbl1059.03034

NotesEmbed ?

top

You must be logged in to post comments.