Valences in Lindenmayer systems

• Autorzy: Fernau H. , Stiebe R.
• Języki publikacji: EN

Abstrakty

EN

We investigate four variants of valence regulations incorporated in (limited) Lindenmayer systems, focussing on hierarchical relations and closure properties. Strong connections to well-known families of languages obtained by regulated rewriting are established. We prove several new results on valence transducers and valence generalized sequential machines (gsm). In this way, we can show new properties of ET0L languages, namely the non-closure under quasiintersection, valence gsm mappings and intersection with regular valence languages. Moreover, we solve a question marked as open in by proving that the uniformly k-limited ET0L languages form a full semi-AFL for all k > 1.

Słowa kluczowe

EN

formal languages; Lindenmayer systems; limited Lindenmayer systems; valence grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 45, nr 4
• Strony: 329--358
• Opis fizyczny: bibliogr. 36 poz.

Twórcy

autor

Fernau H.

autor

Stiebe R.

• Wilhelm-Schickard-Institut für Informatik Universität Tübingen Sand 13, D-72076 Tübingen, Germany,