The Sequence Equivalence Problem for Marked DT0L Systems

• Autorzy: Honkala J.
• Języki publikacji: EN

Abstrakty

EN

We study the DT0L sequence equivalence problem for marked morphisms. We show that to decide this problem it is enough to consider initial terms involving at most 2n morphisms where n is the cardinality of the underlying alphabet.

Słowa kluczowe

EN

DT0L system; DT0L sequence equivalence problem; marked morphism; decidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 175--182
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Honkala J.

• Department of Mathematics University of Turku FI-20014 Turku, Finland,

Bibliografia

• [1] J. Berstel and C. Reutenauer, Rational Series and Their Languages, Springer, Berlin, 1988.
• [2] K. Culik II and J. Karhumäki, A new proof for the D0L sequence equivalence problem and its implications, in G. Rozenberg and A. Salomaa (Eds.), The Book of L, Springer, Berlin, 1986, pp. 63-74.
• [3] V. Halava, T. Harju and M. Hirvensalo, Generalized Post correspondence problem for marked morphisms, Internat. J. Algebra Comput. 10 (2000) 757-772.
• [4] T. Harju, O. Ibarra, J. Karhumäki and A. Salomaa, Some decision problems concerning semilinearity and commutation, J. Comput. System Sci. 65 (2002) 278-294.
• [5] J. Honkala, A short solution for the HDT0L sequence equivalence problem, Theoret. Comput. Sci. 244 (2000) 267-270.
• [6] J. Honkala,Marked D0L systems and the 2n-conjecture, submitted for publication.
• [7] G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems, Academic Press, New York, 1980.
• [8] G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages, Vols. 1-3, Springer, Berlin, 1997.
• [9] A. Salomaa, D0L equivalence: The problem of iterated morphisms, EATCS Bulletin 4 (1978) 5-12.