Checking sets, test sets, rich languages and commutatively closed languages. (English) Zbl 0507.68049


68Q45 Formal languages and automata
Full Text: DOI


[1] Albert, J.; Culik, K.; Karhumäki, J., Test sets for context-free languages and algebraic systems of equations over a free monoid, () · Zbl 0477.68082
[2] Book, R.V.; Brandenburg, F.-J., Equality sets and complexity classes, SIAM J. comput., 9, 729-743, (1980) · Zbl 0446.68040
[3] Culik, K., Some decidability results about regular and pushdown translations, Inform. process. lett., 8, 5-8, (1979) · Zbl 0397.68083
[4] Culik, K., Homomorphisms: decidability, equality, and test sets, (), 167-194
[5] Culik, K.; Diamond, N.D., A homomorphic characterization of time and space complexity classes of languages, Internat. J. comput. math., 8A, 207-222, (1980) · Zbl 0444.68035
[6] Culik, K.; Karhumaki, J., Systems of equations over a free monoid and Ehrenfeucht conjecture, Discrete math., (1982), to appear
[7] Culik, K.; Salomaa, A., On the decidability of homomorphism equivalence for languages, J. comput. system sci., 17, 163-175, (1978) · Zbl 0389.68042
[8] Culik, K.; Salomaa, A., Test sets and checking words for homomorphism equivalence, J. comput. system sci., 20, 379-395, (1980) · Zbl 0451.68046
[9] Ehrenfeucht, A.; Rozenberg, G., Elementary homomorphisms and a solution to the DOL sequence equivalence problem, Theoret. comput. sci., 7, 169-183, (1978) · Zbl 0407.68085
[10] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), NorthHolland Amsterdam · Zbl 0325.68002
[11] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, Mass · Zbl 0411.68058
[12] Hopcroft, J.E.; Ullman, J.D., Formal languages and their relation to automata, (1980), Addison-Wesley Reading, Mass · Zbl 0196.01701
[13] Makanin, G.S., The problem of solvability of equations in a free semigroup, Mat. sb., 103, 145, 148-236, (1977), [Russian] · Zbl 0371.20047
[14] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.