Equational description of pseudovarieties of homomorphisms

Michal Kunc

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 37, Issue: 3, page 243-254
  • ISSN: 0988-3754

Abstract

top
The notion of pseudovarieties of homomorphisms onto finite monoids was recently introduced by Straubing as an algebraic characterization for certain classes of regular languages. In this paper we provide a mechanism of equational description of these pseudovarieties based on an appropriate generalization of the notion of implicit operations. We show that the resulting metric monoids of implicit operations coincide with the standard ones, the only difference being the actual interpretation of pseudoidentities. As an example, an equational characterization of the pseudovariety corresponding to the class of regular languages in AC0 is given.

How to cite

top

Kunc, Michal. "Equational description of pseudovarieties of homomorphisms." RAIRO - Theoretical Informatics and Applications 37.3 (2010): 243-254. <http://eudml.org/doc/92722>.

@article{Kunc2010,
abstract = { The notion of pseudovarieties of homomorphisms onto finite monoids was recently introduced by Straubing as an algebraic characterization for certain classes of regular languages. In this paper we provide a mechanism of equational description of these pseudovarieties based on an appropriate generalization of the notion of implicit operations. We show that the resulting metric monoids of implicit operations coincide with the standard ones, the only difference being the actual interpretation of pseudoidentities. As an example, an equational characterization of the pseudovariety corresponding to the class of regular languages in AC0 is given. },
author = {Kunc, Michal},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {pseudovariety; pseudoidentity; implicit operation; variety of regular languages; syntactic homomorphism.; pseudovarieties; bases of pseudoidentities; implicit operations; varieties of regular languages; syntactic homomorphisms},
language = {eng},
month = {3},
number = {3},
pages = {243-254},
publisher = {EDP Sciences},
title = {Equational description of pseudovarieties of homomorphisms},
url = {http://eudml.org/doc/92722},
volume = {37},
year = {2010},
}

TY - JOUR
AU - Kunc, Michal
TI - Equational description of pseudovarieties of homomorphisms
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 3
SP - 243
EP - 254
AB - The notion of pseudovarieties of homomorphisms onto finite monoids was recently introduced by Straubing as an algebraic characterization for certain classes of regular languages. In this paper we provide a mechanism of equational description of these pseudovarieties based on an appropriate generalization of the notion of implicit operations. We show that the resulting metric monoids of implicit operations coincide with the standard ones, the only difference being the actual interpretation of pseudoidentities. As an example, an equational characterization of the pseudovariety corresponding to the class of regular languages in AC0 is given.
LA - eng
KW - pseudovariety; pseudoidentity; implicit operation; variety of regular languages; syntactic homomorphism.; pseudovarieties; bases of pseudoidentities; implicit operations; varieties of regular languages; syntactic homomorphisms
UR - http://eudml.org/doc/92722
ER -

References

top
  1. J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1995).  
  2. D. Mix Barrington, K. Compton, H. Straubing and D. Thérien, Regular languages in NC1. J. Comput. System Sci.44 (1992) 478-499.  
  3. S. Eilenberg, Automata, Languages and Machines. vol. B, Academic Press, New York (1976).  
  4. J.E. Pin, A variety theorem without complementation. Russian Math. (Iz. VUZ) 39 (1995) 74-83.  
  5. J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1-10.  
  6. M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. and Control 8 (1965) 190-194.  
  7. H. Straubing, On the logical description of regular languages. in Proc. 5th Latin American Sympos. on Theoretical Informatics (LATIN 2002), edited by S. Rajsbaum, Lecture Notes in Comput. Sci., vol. 2286, Springer, Berlin (2002) 528-538.  

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.