Codeterministic Lindenmayer schemes and systems

摘要

A Lindenmayer IL scheme is codeterministic if each string in the alphabet of the scheme is directly derivable from at most one string. Codeterminism is decidable for IL schemes. Equivalence is decidable for codeterministic IL schemes and it is also decidable for DIL schemes. An IL system is codeterministic if each string in the language of the system is directly derivable from at most one string in that language. Although codeterminism is undecidable even for OL systems, it is decidable for those IL systems that generate regular languages. These results concerning IL schemes and systems are obtained by applying the theory of single valued a-transducers after observing: For each IL scheme S there is an a-transducer T(S) such that a string y is directly derivable from a string x via S if and only if y is in T(S)x. Codeterministic OL systems cannot exhibit surface ambiguity, but they may exhibit production ambiguity where these ambiguity concepts are understood in the sense of Reedy and Savitch.