.png){kind=icon}
.png){kind=icon}
Return
Decision Problems Concerning L Systems
.png){kind=icon}
PRE
AI
DOI：10.1007/s00224-025-10246-7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We develop a unified proof technique to study the 0Lness problem (i.e., given a language descriptor, does it generate a 0L language?) across various classes of language descriptors. Notably, we show that the 0Lness problem for linear context-free grammars is productive (a stronger form of non-recursively enumerable), and that it is Co-NEXPTIME-hard for context-free grammars generating finite languages and PSPACE-hard for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{(\cup , \cdot , *)}$$\end{document}-regular expressions. Various decision problems concerning E0L, EDT0L, and ET0L systems are also investigated. These problems include a variety of equivalence and containment problems, and language class comparison problems (e.g., given an arbitrary context-free grammar, does it generate a 0L, DT0L, or EDT0L language?). Most of our results are applicable to promise problems. For example, we show that for a polynomial-time decidable subset of EDT0L systems whose elements only generate regular languages, determining if an element generates a language equal to a fixed unbounded regular set is productive. Analogues of Rice's theorem for E0L, EDT0L, and ET0L systems are developed. We establish that many predicates are either productive or PSPACE-hard for EDT0L and ET0L systems, and either productive or Co-NP-hard for E0L systems.
Keywords:
L systems
Promise problems
0Lness problem
Undecidability
Productiveness
Computational complexity
Journal
T
IF:
0.4
Papers:
43
Citations:
0