\input zb-basic
\input zb-ioport
\iteman{io-port 00985357}
\itemau{Harrison, John}
\itemti{Dynamical properties of PWD0L systems.}
\itemso{Theor. Comput. Sci. 143, No.2, 269-284 (1995).}
\itemab
Summary: The 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^{\ast}.$ The idea of a morphic equivalence relation on $A^{\ast}$ $(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^{\ast}$ made up of all regular languages).
\itemrv{~}
\itemcc{}
\itemut{deterministic zero Lindenmayer scheme; PWD0L systems}
\itemli{doi:10.1016/0304-3975(94)00109-V}
\end