×

The equivalence problem for DF0L languages and power series. (English) Zbl 1059.68062

Summary: We show that equivalence is decidable for D0L systems with finite axiom sets. We discuss also DF0L power series and solve their equivalence problem over computable fields.

MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Berstel, J.; Nielsen, M., The growth range equivalence problem for D0L systems is decidable, (), 161-178
[2] Culik, K.; Fris, I., The decidability of the equivalence problem for D0L-systems, Inform. and control, 35, 20-39, (1977) · Zbl 0365.68074
[3] Culik, K.; Karhumäki, J., A new proof for the D0L sequence equivalence problem and its implications, (), 63-74
[4] Ehrenfeucht, A.; Rozenberg, G., Elementary homomorphisms and a solution of the D0L sequence equivalence problem, Theoret. comput. sci., 7, 169-183, (1978) · Zbl 0407.68085
[5] Honkala, J., The equivalence problem of D0L and DF0L power series, Fund. inform., 38, 201-208, (1999) · Zbl 0935.68061
[6] Honkala, J., On sequences defined by D0L power series, Theoret. inform. appl., 33, 125-132, (1999) · Zbl 0946.68077
[7] Honkala, J., On D0L power series, Theoret. comput. sci., 244, 117-134, (2000) · Zbl 0945.68106
[8] Honkala, J., A short solution for the HDT0L sequence equivalence problem, Theoret. comput. sci., 244, 267-270, (2000) · Zbl 0945.68104
[9] Kuich, W.; Salomaa, A., Semirings, automata, languages, (1986), Springer Berlin
[10] Nielsen, M., On the decidability of some equivalence problems for D0L systems, Inform. and control, 25, 166-193, (1974) · Zbl 0284.68065
[11] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072
[12] Rozenberg, G.; Salomaa, A., Handbook of formal languages, (1997), Springer Berlin · Zbl 0866.68057
[13] Ruohonen, K., On the decidability of the 0L-D0L equivalence problem, Inform. and control, 40, 301-318, (1979) · Zbl 0412.68062
[14] Ruohonen, K., The decidability of the F0L-D0L equivalence problem, Inform. process. lett., 8, 257-260, (1979) · Zbl 0403.68068
[15] Ruohonen, K., The decidability of the D0L-DT0L equivalence problem, J. comput. system sci., 22, 42-52, (1981) · Zbl 0491.68048
[16] Ruohonen, K., On a variant of a method of berstel’s and Nielsen’s, Fund. inform., 4, 369-400, (1981) · Zbl 0475.68044
[17] Ruohonen, K., Equivalence problems for regular sets of word morphisms, (), 393-401
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.