Open AccessThe Growth Range Equivalence Problem for D0L Systems is Decidable
Author(s) -
Jean Berstel
Publication year - 1975
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v4i50.6469
Subject(s) - decidability , equivalence (formal languages) , mathematics , automaton , discrete mathematics , range (aeronautics) , combinatorics , calculus (dental) , computer science , theoretical computer science , medicine , materials science , dentistry , composite material
The decidability of equivalence problems for DOL systems has been studied in various papers. One of the questions left open in these papers, is the decidability of what one might call the growth range equivalence problem. Two DOL systems are said to be equivalent if the ranges of their growth functions coincide. This problem is proved to be decidable. Published in: A. Lindenmayer & G. Rozenberg (ed.) Automata, Languages and Development, North-Holland, 1976.