Decision problems concerning L systems

DOI10.1007/S00224-025-10246-7MaRDI QIDQ6911395zbMATH OpenFDO

Authors Jingnan Xie, H. B. III Hunt, R. E. Stearns

Publication date 24 October 2025

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-025-10246-7

zbMATH Keywords

0Lness problemcomputational complexityL-systemsproductivenesspromise problemsundecidability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Cites work

• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• A note on undecidable properties of formal languages
• Bounded automata groups are co-ET0L
• Complexity of some problems concerningL systems
• Computational Parallels between the Regular and Context-Free Languages
• EDT0L solutions to equations in group extensions
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3521881 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Language-theoretic aspects of DNA complementarity
• Multi-pattern languages
• On Equivalence and Containment Problems for Formal Languages
• On the computational and descriptional complexity of multi-pattern languages
• On the equivalence, containment, and covering problems for the regular and context-free languages
• On the undecidability and descriptional complexity of synchronized regular expressions
• Pumping lemmas can be ``harmful
• The DOL-ness for context-free languages is decidable
• Using \textsc{edt0l} systems to solve some equations in the solvable Baumslag-Solitar groups

This page was built for publication: Decision problems concerning L systems

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