Efficient constructions of test sets for regular and context-free languages. (English) Zbl 0793.68090

This paper involves a nice contribution to a formal language theory. It has been known (Ehrenfeucht conjecture) that, for any language \(L\), there exists a finite test set \(F_ L\) (for each pair of morphisms, if they agree on \(F_ L\), then they agree on the whole set \(L\)). Here, a simple construction of linear size test sets for regular languages and of single exponential test sets for context-free languages is presented. This essentially improves the best known upper bounds: exponential for regular and doubly exponential for context-free languages.


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Aho, A.; Ullman, J., The Theory of Parsing Translation and Compiling, vol. I (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[2] Albert, J.; Culik, K.; Karhuma¨ki, J., Test sets for context-free languages and algebraic systems of equations, Inform. and Control, 52, 172-186 (1982) · Zbl 0522.68064
[3] Albert, M. H.; Lawrence, J., A proof of Ehrenfeucht conjecture, Theoret. Comput. Sci., 41, 121-123 (1985) · Zbl 0602.68066
[4] Blattner, M.; Head, T., The decidability of equivalence for deterministic finite transducers, J. Comput. System Sci., 19, 45-49 (1979) · Zbl 0416.68073
[5] Crochemore, M.; Rytter, W., Parallel computations on strings and arrays, (Proc. STACS. Proc. STACS, Lecture Notes in Computer Science, Vol. 415 (1990), Springer: Springer Berlin), 109-125
[6] Culik, K., Homomorphisms: decidability, equality and test sets, (Book, R., Formal Language Theory, Perspectives and Open Problems (1980), Academic Press: Academic Press New York)
[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, 375-395 (1980) · Zbl 0451.68046
[9] Ehrenfeucht, A.; Karhuma¨ki, J.; Rozenberg, G., On binary equality sets and a solution to the test set conjecture in the binary case, J. Algebra, 85, 76-85 (1983) · Zbl 0523.68066
[10] Gurari, E. M.; Ibarra, O. H., A note on finite valued and finitely ambiguous transducers, Math. Systems Theory, 16, 61-66 (1983) · Zbl 0502.68022
[11] Hopcroft, J.; Ullman, J., Introduction to the Theory of Automata, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[12] Karhuma¨ki, J., The Ehrenfeucht conjecture: a compactness claim for finitely generated free monoids, Theoret. Comput. Sci., 29, 285-308 (1984) · Zbl 0546.68060
[13] Karhuma¨ki, J., On recent trends in formal language theory, (Lecture Notes in Computer Science, Vol. 267 (1987), Springer: Springer Berlin), 136-162
[14] Karp, R.; Miller, R.; Rosenberg, A., Rapid identification of repeated patterns in strings, arrays and trees, Proc. 4th STOC, 125-136 (1972)
[15] Kosaraju, R., Efficient tree pattern matching, Proc. 30th FOCS, 178-183 (1989)
[16] Salomaa, A., Jewels of Formal Language Theory, ((1986), Mir: Mir Moscow), 150 · Zbl 0487.68063
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.