On graph products of automatic monoids

A. Veloso da Costa

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 35, Issue: 5, page 403-417
  • ISSN: 0988-3754

Abstract

top
The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established.

How to cite

top

A. Veloso da Costa. "On graph products of automatic monoids." RAIRO - Theoretical Informatics and Applications 35.5 (2010): 403-417. <http://eudml.org/doc/222022>.

@article{A2010,
abstract = { The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established. },
author = {A. Veloso da Costa},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Automatic monoid; graph product.; graph products; rational languages; automata; automatic monoids},
language = {eng},
month = {3},
number = {5},
pages = {403-417},
publisher = {EDP Sciences},
title = {On graph products of automatic monoids},
url = {http://eudml.org/doc/222022},
volume = {35},
year = {2010},
}

TY - JOUR
AU - A. Veloso da Costa
TI - On graph products of automatic monoids
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 5
SP - 403
EP - 417
AB - The graph product is an operator mixing direct and free products. It is already known that free products and direct products of automatic monoids are automatic. The main aim of this paper is to prove that graph products of automatic monoids of finite geometric type are still automatic. A similar result for prefix-automatic monoids is established.
LA - eng
KW - Automatic monoid; graph product.; graph products; rational languages; automata; automatic monoids
UR - http://eudml.org/doc/222022
ER -

References

top
  1. C.M. Campbell, E.F. Robertson, N. Ruskuc and R.M. Thomas, Automatic Semigroups. Theoret. Comput. Sci. (to appear).  Zbl0987.20033
  2. A.J. Duncan, E.F. Robertson and N. Ruskuc, Automatic monoids and change of generators. Math. Proc. Cambridge Philos. Soc.127 (1999) 403-409.  Zbl0941.20065
  3. E.R. Green, Graph Products of Groups, Ph.D. Thesis. The University of Leeds (1990).  
  4. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979).  Zbl0426.68001
  5. S. Hermiller and J. Meier, Algorithms and Geometry for Graph Products of Groups. J. Algebra171 (1995) 230-257.  Zbl0831.20032
  6. J.M. Howie, An Introduction to Semigroup Theory. Academic Press (1976).  Zbl0355.20056
  7. P.V. Silva and B. Steinberg, A Geometric Characterization of Automatic Monoids. Universidade do Porto (preprint).  Zbl1076.20041
  8. P.V. Silva and B. Steinberg, Extensions and Submonoids of Automatic Monoids. Universidade do Porto (preprint).  Zbl1061.20048
  9. A. Veloso da Costa, Graph Products of Monoids. Semigroup Forum63 (2001) 247-277.  Zbl0992.20042

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.