The language equivalence problem for HD0L systems having D0L growths. (English) Zbl 1078.68086
Summary: We show that language equivalence is decidable for HD0L systems having D0L growths. By definition, an HD0L system \(H\) has D0L growth if the length sequence of \(H\) is a D0L length sequence.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Berstel, J.; Nielsen, M., The growth range equivalence problem for D0L systems is decidable, (Lindenmayer, A.; Rozenberg, G., Automata, Languages and Development (1976), North-Holland: North-Holland Amsterdam), 161-178 |
| [2] | Berstel, J.; Reutenauer, C., Rational Series and Their Languages (1988), Springer: Springer Berlin · Zbl 0668.68005 |
| [3] | Culik II, K.; Fris, I., The decidability of the equivalence problem for D0L-systems, Inform. and Control, 35, 20-39 (1977) · Zbl 0365.68074 |
| [4] | Culik II, K.; Karhumäki, J., A new proof for the D0L sequence equivalence problem and its implications, (Rozenberg, G.; Salomaa, A., The Book of L (1986), Springer: Springer Berlin), 63-74 · Zbl 0586.68066 |
| [5] | 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 |
| [6] | Honkala, J., A short solution for the HDT0L sequence equivalence problem, Theoret. Comput. Sci., 244, 267-270 (2000) · Zbl 0945.68104 |
| [7] | Honkala, J., The equivalence problem for DF0L languages and power series, J. Comput. System Sci., 65, 377-392 (2002) · Zbl 1059.68062 |
| [8] | Honkala, J., On D0L systems with finite axiom sets, Acta Cybernet., 16, 29-35 (2003) · Zbl 1027.68076 |
| [9] | Honkala, J., The DF0L language equivalence problem, Bull. EATCS, 80, 143-152 (2003) · Zbl 1169.68477 |
| [10] | Honkala, J.; Ruohonen, K., On the images of N-rational sequences counting multiplicities, Internat. J. Algebra Comput., 13, 303-321 (2003) · Zbl 1103.68579 |
| [11] | Nielsen, M., On the decidability of some equivalence problems for D0L systems, Inform. and Control, 25, 166-193 (1974) · Zbl 0284.68065 |
| [12] | Rozenberg, G., The equivalence problem for deterministic T0L systems is undecidable, Inform. Process. Lett., 1, 201-204 (1972) · Zbl 0267.68033 |
| [13] | Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072 |
| [14] | G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 1-3, Springer, Berlin, 1997.; G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 1-3, Springer, Berlin, 1997. · Zbl 0866.68057 |
| [15] | Ruohonen, K., On the decidability of the 0L-D0L equivalence problem, Inform. and Control, 40, 301-318 (1979) · Zbl 0412.68062 |
| [16] | Ruohonen, K., The decidability of the F0L-D0L equivalence problem, Inform. Process. Lett., 8, 257-260 (1979) · Zbl 0403.68068 |
| [17] | Ruohonen, K., The inclusion problem for D0L languages, Elektron. Informationsverarbeit. Kybernet., 15, 535-548 (1979) · Zbl 0428.68081 |
| [18] | Ruohonen, K., On a variant of a method of Berstel’s and Nielsen’s, Fund. Inform., 4, 369-400 (1981) · Zbl 0475.68044 |
| [19] | Ruohonen, K., The decidability of the D0L-DT0L equivalence problem, J. Comput. System Sci., 22, 42-52 (1981) · Zbl 0491.68048 |
| [20] | Ruohonen, K., Equivalence problems for regular sets of word morphisms, (Rozenberg, G.; Salomaa, A., The Book of L (1986), Springer: Springer Berlin), 393-401 · Zbl 0612.68052 |
| [21] | K. Ruohonen, Test sets for iterated morphisms, Report 49, Tampere University of Technology, Tampere, 1986.; K. Ruohonen, Test sets for iterated morphisms, Report 49, Tampere University of Technology, Tampere, 1986. · Zbl 0612.68052 |
| [22] | Salomaa, A., On sentential forms of context-free grammars, Acta Informat., 2, 40-49 (1973) · Zbl 0264.68029 |
| [23] | Salomaa, A., Simple reductions between D0L language and sequence equivalence problems, Discrete Appl. Math., 41, 271-274 (1993) · Zbl 0788.68086 |
| [24] | Salomaa, A.; Soittola, M., Automata-Theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039 |
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.
