The Sequence Equivalence Problem for Marked DT0L Systems

Issue title: Theory that Counts: To Oscar Ibarra on His 70th Birthday

Article type: Research Article

Authors: Honkala, Juha

Affiliations: Department of Mathematics, University of Turku, FI-20014 Turku, Finland. [email protected]

Note: [] Address for correspondence: Department of Mathematics, University of Turku, FI-20014 Turku, Finland

Abstract: 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.

Keywords: DT0L system, DT0L sequence equivalence problem, marked morphism, decidability

DOI: 10.3233/FI-2011-535

Journal: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 175-182, 2011