Abstract
We show that for every context free language L over some alphabet Σ there effectively exists a test set F, that is a finite subset of L such that, for any pair (g,h) of homomorphisms on Σ*, g(x)=h(x) for each × in F implies g(x)=h(x) for all × in L.
This result is then extended from homomorphisms to deterministic generalized sequential machine mappings defined by machines with uniformly bounded number of states.
This research was supported by the National Sciences and Engineering Council of Canada, under Grant No. A7403.
This paper was written during the first author's visit at the University of Waterloo, Waterloo, Ontario, Canada.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albert, J. and Culik, K. II (1979), Test sets for homomorphisms equivalence on context free languages, Inf. and Control, to appear, also Res. Rep. CS-79-39, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada.
Blattner, M. and Head, T. (1979), The decidability of equivalence for deterministic finite transducers, J. Computer Syst. Sci. 19, 45–49.
Culik, K. II (1977), On the decidability of the sequence equivalence problem for DOL-systems, Theoretical Computer Sci. 3, 75–84.
Culik, K. II (1979), Some decidability results about regular and push down translations, Information Processing Letters 8, 5–8.
Culik, K. II (1980), Homomorphisms: Decidability, Equality and Test Sets, Proceedings of the International Symposium on Formal Languages Theory, Santa Barbara, California, Dec. 1979, to appear, also Res. Rep. CS-80-02, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada.
Culik, K. II and Fris, I. (1977), The decidability of the equivalence problem for DOL systems, Inform. Control 35, 20–39.
Culik, K. II and Richier, J.L. (1979), Homomorphism equivalence on ETOL languages, Int. J. Computer Math. Section A, 7, 43–51.
Culik, K. II and Salomaa, A. (1978), On the decidability of homomorphism equivalence for languages, J. Computer Syst. Sci. 17, 163–175.
Culik, K. II and Salomaa, A. (1979), Test sets and checking words for homomorphism equivalence, J. Computer Syst. Sci., to appear, also Res. Rep. CS-79-04, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada.
Harrison, M.A. (1978), "Introduction to Formal Language Theory", Addison-Wesley, Reading, Massachusetts.
Hopcroft, J.E. and Ullman, J.D. (1969), "Formal Languages and Their Relation to Automata", Addison-Wesley, Reading, Massachusetts.
Salomaa, A. (1973), "Formal Languages", Academic Press, New York.
Salomaa, A. (1978), Equality sets for homomorphisms on free monoids, Acta Cybernetica, vol. 4, 127–139.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1980 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Albert, J., Culik, K. (1980). Test sets for homomorphism equivalence on context free languages. In: de Bakker, J., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 1980. Lecture Notes in Computer Science, vol 85. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10003-2_55
Download citation
DOI: https://doi.org/10.1007/3-540-10003-2_55
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-10003-4
Online ISBN: 978-3-540-39346-7
eBook Packages: Springer Book Archive