The pseudovariety is hyperdecidable
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1997)
- Volume: 31, Issue: 5, page 457-482
- ISSN: 0988-3754
Access Full Article
top
How to cite
topAlmeida, 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. 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. J. ALMEIDA, The algebra of implicit operations, Algebra Universalis, 1989, 26, pp. 16-32. Zbl0671.08003MR981423
- 3. J. ALMEIDA, Finite Semigroups and Universal Algebra, volume 3 of Series in Algebra. World Scientific, 1995. English translation. Zbl0844.20039MR1331143
- 4. J. ALMEIDA, Hyperdecidable pseudovarieties and the calculation of semidirect products. Technical Report 96-11, Universidade do Porto (Portugal), 1997. Zbl1028.20038
- 5. J. ALMEIDA, Some algorithmic problems for pseudovarieties. In AFL'96, to appear. Technical Report 96-9, Universidade do Porto (Portugal). MR1709911
- 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. 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. K. HENCKELL, Pointlike sets: the finest aperiodic cover of a finite semigroup, J. Pure Appl. Algebra, 1988, 55, pp. 85-126. Zbl0682.20044MR968571
- 9. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata theory, Languages and Computation, Addison-Wesley, 1979. Zbl0426.68001MR645539
- 10. J.-É. PIN, Varieties of Formal Languages, Plenum Press, 1986. Zbl0632.68069MR912694
- 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. 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. M. ZEITOUN, On the decidability of the membership problem of the pseudovariety J ν B , Internat. J. Algebra Comput, 1994, 4, (4) Zbl0832.20081MR1318822
NotesEmbed ?
topYou 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.