EDT0L grammars with only one variable have tractable generating functions

DOI10.1051/ITA/2023004MaRDI QIDQ6047790zbMATH OpenOpenAlexFDO

Authors Eric Freden

Publication date 13 September 2023

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/ita/2023004

zbMATH Keywords

EDT0Lgenerating functionsLindemayer systems

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15)

Cites work

• A Gap Theorem for Power Series Solutions of Algebraic Differential Equations
• Applications of L systems to group theory
• Controlled iteration grammars and full hyper-AFL's
• Free subgroups in linear groups
• From indexed grammars to generating functions
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3684912 (Why is no real title available?)
• scientific article; zbMATH DE number 1747441 (Why is no real title available?)
• scientific article; zbMATH DE number 3802813 (Why is no real title available?)
• scientific article; zbMATH DE number 770291 (Why is no real title available?)
• scientific article; zbMATH DE number 848094 (Why is no real title available?)
• Indexed Grammars—An Extension of Context-Free Grammars
• Nested Stack Automata
• On ambiguity in EOL systems
• On inherently ambiguous E0L languages
• On some families of languages related to developmental systems
• ON THE DESCRIPTIONAL COMPLEXITY OF LINDENMAYER SYSTEMS
• On the entropy of context-free languages
• ON THE NUMBER OF ACTIVE SYMBOLS IN LINDENMAYER SYSTEMS
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• The structure generating function of some families of languages
• TOL schemes and control sets

Cited in

(1)

• Lambek Grammars with One Division Are Decidable in Polynomial Time

This page was built for publication: EDT0L grammars with only one variable have tractable generating functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047790)