The pseudovariety J is hyperdecidable

J. Almeida; M. Zeitoun

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

  • Volume: 31, Issue: 5, page 457-482
  • ISSN: 0988-3754

How to cite

top

Almeida, J., and Zeitoun, M.. "The pseudovariety $J$ is hyperdecidable." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 31.5 (1997): 457-482. <http://eudml.org/doc/92573>.

@article{Almeida1997,
author = {Almeida, J., Zeitoun, M.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {pseudovarieties of finite semigroups; implicit operations; pseudovariety closure of languages; decidable problems; hyperdecidability; recognizable languages; emptiness problem},
language = {eng},
number = {5},
pages = {457-482},
publisher = {EDP-Sciences},
title = {The pseudovariety $J$ is hyperdecidable},
url = {http://eudml.org/doc/92573},
volume = {31},
year = {1997},
}

TY - JOUR
AU - Almeida, J.
AU - Zeitoun, M.
TI - The pseudovariety $J$ is hyperdecidable
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1997
PB - EDP-Sciences
VL - 31
IS - 5
SP - 457
EP - 482
LA - eng
KW - pseudovarieties of finite semigroups; implicit operations; pseudovariety closure of languages; decidable problems; hyperdecidability; recognizable languages; emptiness problem
UR - http://eudml.org/doc/92573
ER -

References

top
  1. 1. D. ALBERT, R. BALDINGER and J. RHODES, Undecidability of the identity problem for finite semigroups, J. Symbolic Logic, 1992, 57, (1), pp.179-192. Zbl0780.20035MR1150933
  2. 2. J. ALMEIDA, The algebra of implicit operations, Algebra Universalis, 1989, 26, pp. 16-32. Zbl0671.08003MR981423
  3. 3. J. ALMEIDA, Finite Semigroups and Universal Algebra, volume 3 of Series in Algebra. World Scientific, 1995. English translation. Zbl0844.20039MR1331143
  4. 4. J. ALMEIDA, Hyperdecidable pseudovarieties and the calculation of semidirect products. Technical Report 96-11, Universidade do Porto (Portugal), 1997. Zbl1028.20038
  5. 5. J. ALMEIDA, Some algorithmic problems for pseudovarieties. In AFL'96, to appear. Technical Report 96-9, Universidade do Porto (Portugal). MR1709911
  6. 6. J. ALMEIDA and P. V. SILVA, On the hyperdecidability of semidirect products of pseudovarieties. Technical Report 97-20, Universidade do Porto (Portugal), 1997. Zbl0931.20047MR1661260
  7. 7. C. J. ASH, Inevitable graphs: a proof of the type II conjecture and some related decision procedures, Internat. J. Algebra Comput., 1991, 1, pp. 127-146. Zbl0722.20039MR1112302
  8. 8. K. HENCKELL, Pointlike sets: the finest aperiodic cover of a finite semigroup, J. Pure Appl. Algebra, 1988, 55, pp. 85-126. Zbl0682.20044MR968571
  9. 9. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata theory, Languages and Computation, Addison-Wesley, 1979. Zbl0426.68001MR645539
  10. 10. J.-É. PIN, Varieties of Formal Languages, Plenum Press, 1986. Zbl0632.68069MR912694
  11. 11. J. RHODES, New techniques in global semigroup theory. In S. Goberstein and P. Higgins, editors, Semigroups and their Applications, D. Reidel, 1987, pp. 168-181. Zbl0622.20049MR900657
  12. 12. I. SIMON, Piecewise testable events. In Proc. 2nd GI Conf., volume 33 of Lect. Notes Comp. Sci., Springer-Verlag, 1975, pp. 214-222. Zbl0316.68034MR427498
  13. 13. M. ZEITOUN, On the decidability of the membership problem of the pseudovariety J ν B , Internat. J. Algebra Comput, 1994, 4, (4) Zbl0832.20081MR1318822

NotesEmbed ?

top

You must be logged in to post comments.