Marked D0L systems and the \(2n\)-conjecture. (English) Zbl 1242.68145
Summary: We show that to test the equivalence of two D0L sequences over an \(n\)-letter alphabet generated by marked morphisms it suffices to compare the first \(2n+1\) initial terms of the sequences. Under an additional condition it is enough to consider the 2n initial terms.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Berstel, J.; Reutenauer, C., Rational Series and Their Languages (1988), Springer: Springer Berlin · Zbl 0668.68005 |
| [2] | Culik II, K.; Fris, I., The decidability of the equivalence problem for D0L-systems, Inform. Control, 35, 20-39 (1977) · Zbl 0365.68074 |
| [3] | 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 |
| [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., A short solution for the HDT0L sequence equivalence problem, Theoret. Comput. Sci., 244, 267-270 (2000) · Zbl 0945.68104 |
| [6] | Karhumäki, J., On the equivalence problem for binary D0L systems, Inform. Control, 50, 276-284 (1981) · Zbl 0497.68048 |
| [7] | Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072 |
| [8] | (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, Vols. 1-3 (1997), Springer: Springer Berlin) · Zbl 0866.68057 |
| [9] | 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 |
| [10] | 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 |
| [11] | Ruohonen, K., Explicit test sets for iterated morphisms in free monoids and metabelian groups, Theoret. Comput. Sci., 330, 171-191 (2005) · Zbl 1078.68094 |
| [12] | Ruohonen, K., D0L sequence equivalence is in P for fixed alphabets, Theor. Inform. Appl., 42, 361-374 (2008) · Zbl 1144.68037 |
| [13] | Salomaa, A., D0L equivalence: The problem of iterated morphisms, EATCS Bulletin, 4, 5-12 (1978) |
| [14] | 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.
