The Equivalence Problem of Polynomially Bounded D0L Systems— a Bound Depending Only on the Size of the Alphabet

Abstract

Abstract. We give a bound for the sequence equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.

Similar content being viewed by others

A new bound for the D0L language equivalence problem

Article 24 November 2016

Descriptive Complexity of Deterministic Polylogarithmic Time

Chapter © 2019

IntegerSequences: A Package for Computing with k-Regular Sequences

Chapter © 2018

Author information

Authors and Affiliations

1. Department of Mathematics, University of Turku, juha.honkala@utu.fi, FIN-20014 Turku, Finland, FI

   Juha Honkala

Authors

1. Juha Honkala
   View author publications

   You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Honkala, J. The Equivalence Problem of Polynomially Bounded D0L Systems— a Bound Depending Only on the Size of the Alphabet . Theory Comput. Systems 36, 89–103 (2003). https://doi.org/10.1007/s00224-002-1075-1

Download citation

• Published: 20 January 2003

• Issue Date: February 2003

• DOI: https://doi.org/10.1007/s00224-002-1075-1

Keywords

• Equivalence Problem
• Initial Term
• Distinct Letter
• Arbitrary Morphism
• Monoid Morphism