A-transducers and the monotonicity of IL schemes

摘要

A Lindenmayer IL scheme is monotonic if no string in the alphabet of the scheme directly derives a strictly shorter string. An IL system is monotonic if no string in the language of the system directly derives a strictly shorter string. Monotonic schemes are a generalization of propogating schemes and many results and algorithms in the literature of Lindenmayer theory that are stated for propogating schemes and systems also hold for monotonic schemes and systems. Thus when a scheme or system can be recognized to be monotonic, many conclusions and algorithms are available for its study. In this article it is shown that monotonicity of IL schemes is decidable and that monotonicity of those IL systems that generate regular languages is decidable. These results are obtained by converting IL schemes into a-transducers and then deciding monotonicity for the resulting a-transducers.