×

zbMATH — the first resource for mathematics

The decidability of the DOL-DTOL equivalence problem. (English) Zbl 0491.68048

MSC:
68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
03D40 Word problems, etc. in computability and recursion theory
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berstel, J.; Nielsen, M., The growth range equivalence problem for DOL systems is decidable, (), 161-178
[2] Blattner, M., The unsolvability of the equality problem for sentential forms of context-free languages, J. comput. system sci., 7, 463-468, (1973) · Zbl 0273.68054
[3] Čulik, K.; Friš, I., The decidability of the equivalence problem for DOL systems, Inform. contr., 35, 20-39, (1977) · Zbl 0365.68074
[4] Ehrenfeucht, A.; Rozenberg, G., Elementary homomorphisms and a solution of the DOL sequence equivalence problem, Theoret. comput. sci., 7, 169-184, (1978) · Zbl 0407.68085
[5] Herman, G.T.; Rozenberg, G., Developmental systems and languages, (1975), North-Holland Amsterdam · Zbl 0313.68068
[6] Karhumäki, J.; Simon, I., A note on elementary homomorphisms and the regularity of equality sets, Bull. EATCS, No. 9, 16-24, (1979)
[7] Nielsen, M., On the decidability of some equivalence problems for DOL systems, Inform. contr., 25, 166-193, (1974) · Zbl 0284.68065
[8] Rozenberg, G., Direct proofs of the undecidability of the equivalence problem for sentential forms of linear context-free grammars and the equivalence problem for 0L systems, Inform. process. lett., 1, 233-235, (1972) · Zbl 0249.68029
[9] Rozenberg, G., The equivalence problem for deterministic TOL systems is undecidable, Inform. process. lett., 1, 201-204, (1972) · Zbl 0267.68033
[10] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (), 161-206 · Zbl 0365.68072
[11] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072
[12] Ruohonen, K., A note on language equations involving morphisms, Inform. process. lett., 7, 209-212, (1978) · Zbl 0385.68058
[13] Ruohonen, K., The inclusion problem for DOL languages, Elektron. informationsverarbeit. kybernetik, 15, 535-548, (1979) · Zbl 0428.68081
[14] Ruohonen, K., On the decidability of the OL-DOL equivalence problem, Inform. contr., 40, 301-318, (1979) · Zbl 0412.68062
[15] Ruohonen, K., The decidability of the FOL-DOL equivalence problem, Inform. process. lett., 8, 257-260, (1979) · Zbl 0403.68068
[16] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
[17] Salomaa, A., On sentential forms of context-free languages, Acta inform., 2, 40-49, (1973) · Zbl 0264.68029
[18] Vitanyi, P.M.B., On the size of DOL languages, (), 78-92 · Zbl 0252.68042
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.