Dynamical properties of PWD0L systems

AbstractThe definitions of a piecewise deterministic zero Lindenmayer (PWD0L) scheme and system are given, and dynamical properties of such systems are introduced. Harrison (1994) showed that given an arbitrary finite alphabet A, the emptiness problem is undecidable for the class of languages which are intersections of a D0L language and a context-sensitive language. This result is used to prove that many dynamical properties of PWD0L systems(such as finiteness, periodicity, etc) are in general undecidable over a two-member context-sensitive partition of A∗.The idea of a morphic equivalence relation on A∗ (A is finite) is defined and the idea of a finite morphic refinement is introduced. Harrison (1994) showed that every regular language and its complement is refined by a finite partition which is induced by a morphic congruence. Using this theorem, it is shown that dynamical properties such as finiteness and periodicity are in general decidable for RWD0L systems (i.e. a PWD0L system over a finite partition of A∗ made up of all regular languages)