On recent trends in formal language theory | SpringerLink
Skip to main content
Springer Nature Link
Log in

On recent trends in formal language theory

  • Formal Languages And Automata
  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1987)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 267))

Included in the following conference series:

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Albert, J., Culik II, K. and Karhumaki J. Test sets for context-free languages and algebraic systems of equations, Inform. Control 52 (1982) 172–186.

    Article  Google Scholar 

  2. Albert, M.H. and Lawrence J., A proof of Ehrenfeucht's Conjecture, Theoret. Comput. Sci. 41 (1985) 121–123.

    Article  Google Scholar 

  3. Albert, M.H. and Lawrence J., Test sets for finite substitutions, Theoret. Comput. Sci. 43 (1986) 117–122.

    Google Scholar 

  4. Berstel, J., Transductions and Context-Free Languages (Teubner, Stuttgard, 1979).

    Google Scholar 

  5. Berstel, J. and Perrin, D., Theory of Codes (Academic Press, New York, 1986).

    Google Scholar 

  6. Bird, M., The equivalence problem for deterministic two-tape automata, J. Comput. System Sci. 7 (1973) 218–236.

    Google Scholar 

  7. Book, R. and Brandenburg F.-J., Equality sets and complexity classes, SIAM J. Comput. 9 (1980) 729–743.

    Google Scholar 

  8. Brandenburg, F.-J., A truly morphic characterization of recursively enumerable sets, LNCS 176 (1984) 205–213.

    Google Scholar 

  9. Claus, V., Some remarks on PCP(k) and related problems, Bull. EATCS 12 (1980) 54–61.

    Google Scholar 

  10. Choffrut, C. and Karhumaki, J., Test sets for morphisms with bounded delay, Discret. Appl. Math. 12 (1985) 93–101.

    Google Scholar 

  11. Culik II, K., A purely homomorphic characterization of recursively enumerable sets, J. Assoc. Comput. Mach. 6 (1979) 345–350.

    Google Scholar 

  12. Culik II, K., Homomorphisms: Decidability, Equality and Test Sets, in R. Book (ed.), Formal Language Theory, Perspectives and Open Problems (Academic Press, New York, 1980).

    Google Scholar 

  13. Culik II, K. and Fris, I., The decidability of the equivalence problem for DOL-systems, Inform. Control 33 (1977) 20–39.

    Google Scholar 

  14. Culik II, K., Fich, F.E. and Salomaa, A., A homomorphic characterization of regular languages, Discret. Appl. Math. 4 (1982) 149–152.

    Google Scholar 

  15. Culik II, K. and Karhumaki, J., On equality sets for homomorphisms on free monoids with two generators. RAIRO Theor. Inform. 14 (1980) 349–369.

    Google Scholar 

  16. Culik II, K. and Karhumaki, J., Systems of equations over a free monoid and Ehrenfeucht's Conjecture, Discret. Math. 43 (1983) 139–153.

    Article  Google Scholar 

  17. Culik II, K. and Karhumaki, J., A new proof for the DOL sequence equivalence problem and its implications, in G. Rozenberg and A. Salomaa (eds), The Book of L (Springer, Berlin,1986).

    Google Scholar 

  18. Culik II,K. and Karhumaki,J., The equivalence problem for single-valued two-way transducers (on NPDTOL languages) is decidable, SIAM J. Comput. (to appear).

    Google Scholar 

  19. Culik II, K. and Karhumaki, J., The equivalence of finite valued transducers (on HDTOL languages) is decidable, Theoret. Comput. Sci. 47 (1986) 71–84.

    Article  Google Scholar 

  20. Culik II,K. and Karhumaki,J., Systems of equations over a finitely generated free monoid having an effectively findable equivalent finite susbsystem, manuscript (1986).

    Google Scholar 

  21. Culik II, K. and Diamond, N.D., A homomorphic characterization of time and space complexity classes, Int. J. Comput. Math. 8 (1980) 207–222.

    Google Scholar 

  22. Culik II, K. and Maurer, H., On simple representation of language families, RAIRO Theor. Inform. 13 (1979) 241–250.

    Google Scholar 

  23. Culik II, K. and Salomaa, A., On the decidability of homomorphism equivalence for languages. J. Comput. System Sci. 17 (1978) 163–175.

    Article  Google Scholar 

  24. Culik II, K. and Salomaa, A., Test sets and checking words for homomorphism equivalence, J. Comput. System Sci. 20 (1980) 375–395.

    Article  Google Scholar 

  25. Ehrenfeucht, A., Karhumaki, J. and Rozenberg, G., The (generalized) Post Correspondence Problem with lists consisting of two words is decidable, Theoret. Comput. Sci. 21 (1982) 119–144.

    Article  Google Scholar 

  26. Ehrenfeucht, A., Karhumaki, J. and Rozenberg, G., On binary equality sets and a solution to the test set conjecture in the binary case, J. Alg. 85 (1983) 76–85.

    Article  Google Scholar 

  27. Ehrenfeucht, A. and Rozenberg, G., Elementary homomorphisms and a solution to DOL sequence equivalence problem. Theoret. Comput. Sci. 7 (1978) 169–183.

    Article  Google Scholar 

  28. Ehrenfeucht, A. and Rozenberg, G., On a bound for the DOL sequence equivalence problem, Theoret. Comput. Sci. 12 (1980) 339–342.

    Article  Google Scholar 

  29. Eilenberg, S., Automata, Languages and Machines, vol.A (Academic Press, New York, 1974).

    Google Scholar 

  30. Engelfriet, J. and Rozenberg, G., Equality languages and fixed point languages, Inform. Control 43 (1979) 20–49.

    Article  Google Scholar 

  31. Engelfriet, J. and Rozenberg, G., Fixed point languages, equality languages and representation of recursively enumerable languages, J. Assoc. Comput. Mach. 27 (1980) 499–518.

    Google Scholar 

  32. Gersten,S.M., Fixed points of automorphisms of free groups, Adv. in Math. (to appear).

    Google Scholar 

  33. Greibach, S., A remark on code sets and context-free languages, IEEE Trans. Comput. C-24 (1975) 741–742.

    Google Scholar 

  34. Griffiths, T., The unsolvability of the equivalence problem for ɛ-free nondeterministic generalized machines, J. Assoc. Comput. Mach. 15 (1968) 409–413.

    Google Scholar 

  35. Guba,V.S., Personal communication (1985).

    Google Scholar 

  36. Harrison, M.A., Introduction to Formal Language Theory (Addison-Wesley, Reading, MA, 1979).

    Google Scholar 

  37. Harju, T. and Karhumaki, J., On the defect theorem and simplifiability, Semigroup Forum 33 (1986) 199–217.

    Google Scholar 

  38. Harju, T., Karhumaki, J. and Kleijn, H.C.M., On morphic generation of regular languages, Discret. Appl. Math. 15 (1986) 55–60.

    Article  Google Scholar 

  39. Hirose, S. and Yoneda, M., On the Chomsky and Stanley's homomorphic characterization of context-free languages, Theoret. Comput. Sci. 36 (1985) 109–112.

    Article  Google Scholar 

  40. Hirose, S., Okawa, S. and Yoneda, M., A homomorphic characterization of recursively enumerable languages, Theoret. Comput. Sci. 35 (1985) 261–269.

    Article  Google Scholar 

  41. Ibarra,O. and Kim,C., A useful device for showing the solvability of some decision problems. in Proceedings of Eighth Annual ACM Symposium on Theory of Computing, 135–140.

    Google Scholar 

  42. Karhumaki, J., Generalized Parikh mappings and homomorphisms, Inform. Control 47 (1980) 155–165.

    Article  Google Scholar 

  43. Karhumaki, J., On the equivalence problem for binary DOL systems, Inform. Control 50 (1981) 276–284.

    Article  Google Scholar 

  44. Karhumaki, J., The Ehrenfeucht Conjecture: A compactness claim for finitely generated free monoids, Theoret. Comput. Sci. 29 (1984) 285–308.

    Article  Google Scholar 

  45. Karhumaki,J., On the regularity of equality languages, Ann. Univ. Turkuensis Ser. A I 186 (1984).

    Google Scholar 

  46. Karhumaki,J., The Ehrenfeucht Conjecture for transducers, Elektron. Informationsverarb. Kybernet. (to appear).

    Google Scholar 

  47. Karhumaki,J., On the equivalence of mappings on languages, in Proceedings of International Meeting of Young Computer Scientists (Hungarian Academy of Sciences, 1986).

    Google Scholar 

  48. Karhumaki, J. and Kleijn, H.C.M., On the equivalence of compositions of morphisms and inverse morphisms on regular languages, RAIRO Theoret. Inform. 19 (1985) 203–211.

    Google Scholar 

  49. Karhumaki, J. and Linna, M., A note on morphic characterization of languages, Discret. Appl. Math. 5 (1983) 243–246.

    Article  Google Scholar 

  50. Karhumaki, J. and Maon, Y., A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language, J. Comput. System Sci. 32 (1986) 315–322.

    Article  Google Scholar 

  51. Karhumaki, J. and Simon, I., A note on elementary homorphisms and the regularity of equality sets, Bull.EATCS 9 (1975) 14–24.

    Google Scholar 

  52. Lawrence, J., The non-existence of finite test sets for set-equivalence of finite substitutions, Bull. EATCS 28 (1986) 34–37.

    Google Scholar 

  53. Latteux, M. and Leguy, J., On the composition of morphisms and inverse morphisms, LNCS 154 (1983) 420–432.

    Google Scholar 

  54. Latteux,M. and Turakainen,P., A new normal form for compositions of morphisms and inverse morphisms, manuscript (1984).

    Google Scholar 

  55. Lecerf, Y., Recursive insolubilité de l'equation generale de diagonalization de deux monomorphisms de monoides libres φx=ψx, L.R. Acad.Sci. Paris 257 (1963) 2940–2943.

    Google Scholar 

  56. Lothaire, M., Combinatorics on words (Addison-Wesley, Reading, MA, 1983).

    Google Scholar 

  57. de Luca, A. and Restivo, A., On a generalization of a conjecture of Ehrenfeucht, Bull.EATCS 30 (1986) 84–90.

    Google Scholar 

  58. Makanin, G.S., The problem of solvability of equations in a free semigroup, Mat. Sb. 103 (1977) 147–836 (English transl. in: Math. USSR Sb. 32 (1977) 129–138).

    Google Scholar 

  59. Matijasevic, J.V., Simple examples of undecidable associative calculi, Soviet Math. Dokl. 8 (1967) 555–557.

    Google Scholar 

  60. McNaughton,R., A proof of the Ehrenfeucht conjecture, Informal Memorandum (1985).

    Google Scholar 

  61. Maon,Y., Decision problems concerning equivalence of transductions on languages, Ph.D. Thesis, Tel Aviv University (1985).

    Google Scholar 

  62. Nielsen, M., On the decidability of some equivalence problems for DOL systems, Inform. Control 25 (1974) 166–193.

    Article  Google Scholar 

  63. Okama, S., Hirose, S. and Yoneda, M., On the impossibility of the homorphic characterization of context-sensitive languages, Theoret. Comput. Sci. 44 (1986) 225–228.

    Article  Google Scholar 

  64. Pansiot, J.J., A note on Post's Correspondence Problem, Inform. Proc. Lett. 12 (1981) 233.

    Article  Google Scholar 

  65. Pavlenko,V.A., Combinatorial problem of Post with two word pairs, Proceedings of 7th Conference on Mathematical Logic, Novosibirsk, Institute of Mathematics, Siberian Branch of Academy of Sciences of USSR (1984).

    Google Scholar 

  66. Perrin, D., On the solution of Ehrenfeucht's conjecture, Bull. EATCS 27 (1985) 68–70.

    Google Scholar 

  67. Post, E.L., A variant of recursively unsolvable problems, Bull. Amer. Math. Soc. 52 (1946) 264–268.

    Google Scholar 

  68. Poulsen, E.T., The Ehrenfeucht conjecture: An algebra-framework for its proof, Theoret. Comput. Sci. 44 (1986) 333–339.

    Article  Google Scholar 

  69. Rozenberg, G. and Salomaa, A., The Mathematical Theory of L Systems, (Academic Press, New York, 1980)

    Google Scholar 

  70. Ruohonen, K., On some variants of Post's Correspondence Problem, Acta Informatica 19 (1983) 357–367.

    Article  Google Scholar 

  71. Ruohonen, K., Reversible machines and Post's Correspondence Problem for biprefix morphisms, Elektron. Informationsverarb. Kybernet. 21 (1985) 579–596).

    Google Scholar 

  72. Ruohonen,K., Test sets for iterated morphisms, manuscript (1984).

    Google Scholar 

  73. Ruohonen, K., Equivalence problems for regular sets of word morphisms, in. G. Rozenberg and A. Salomaa (eds), The Book of L (Springer, Berlin, 1986).

    Google Scholar 

  74. Salomaa, A., Equality sets for homomorphisms of free monoids, Acta Cybernetica 4 (1978) 197–139.

    Google Scholar 

  75. Salomaa, A., DOL equivalence: The problem of iterated morphisms, Bull.EATCS 4 (1978) 5–12.

    Google Scholar 

  76. Salomaa, A., Jewels of Formal Languages (Computer Science Press, Rockville, MD, 1981).

    Google Scholar 

  77. Salomaa, A., The Ehrenfeucht conjecture: A proof for language theorists, Bull.EATCS 27 (1985) 71–82.

    Google Scholar 

  78. Spehner, J.-G., Personal communication (1986).

    Google Scholar 

  79. Stallings, J.R., Finiteness properties of matrix representations, Ann. Math. 124 (1986) 337–346.

    Google Scholar 

  80. Stallings,J.R., Graphical theory of automorphisms of free groups, manuscript.

    Google Scholar 

  81. Turakainen, P., On homorphic characterization of principal semi-AFL's without using intersection with regular sets, Inform.Sci. 27 (1982) 141–149.

    Article  Google Scholar 

  82. Turakainen, P., On characterization of language families in terms of inverse morphisms, Internat. J. Comput. Math. 16 (1984) 182–200.

    Google Scholar 

  83. Turakainen,P., Characterizations of simple transducers and principal semiAFL's in terms of morphisms and inverse morphisms, Elektron. Informationverarb. Kybernet. (to appear).

    Google Scholar 

  84. Turakainen,P., On some transducer equivalence problems for families of languages, manuscript (1987).

    Google Scholar 

  85. Yokomori, T. and Wood, D., An inverse homomorphic characterization of full principal AFL, Inform. Sci. 33 (1984) 209–215.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Turku, Turku, Finland

    Juhani Karhumäki

Authors
  1. Juhani Karhumäki
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Thomas Ottmann

Rights and permissions

Reprints and permissions

Copyright information

© 1987 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Karhumäki, J. (1987). On recent trends in formal language theory. In: Ottmann, T. (eds) Automata, Languages and Programming. ICALP 1987. Lecture Notes in Computer Science, vol 267. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18088-5_12

Download citation

  • DOI: https://doi.org/10.1007/3-540-18088-5_12

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-18088-3

  • Online ISBN: 978-3-540-47747-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation