Decision Problems Concerning L Systems

doi:10.1007/s00224-025-10246-7

2025-10-11

PRE

Jingnan Xie *

Harry B. Hunt

Richard E. Stearns

DOI：10.1007/s00224-025-10246-7

原文链接

原文求助

摘要

En 中文

我们提出了一种统一的证明方法来研究0L性判定问题（即，给定一个语言描述器，它是否生成0L语言？），该问题跨越了各种语言描述器类。值得注意的是，我们证明了线性上下文无关文法的0L性问题是可生成问题（非递归可枚举的一种更强形式），而对于生成有限语言的上下文无关文法，该问题是Co-NEXPTIME难的，而对于\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}-正则表达式，该问题是PSPACE难的。我们还研究了关于E0L、EDT0L和ET0L系统的各类判定问题。这些问题包括各种等价性和包含性问题，以及语言类比较问题（例如，给定一个任意的上下文无关文法，它是否生成0L、DT0L或EDT0L语言？）。我们的大部分结果同样适用于承诺问题。例如，我们证明了对于EDT0L系统的一个多项式时间可判定的子集，其元素仅生成正则语言，确定某个元素是否生成一个与固定无界正则集相等的语言是一个可生成问题。我们发展了适用于E0L、EDT0L和ET0L系统的Rice定理类比。我们证明了对于EDT0L和ET0L系统，许多谓词要么是可生成的，要么是PSPACE难的，而对于E0L系统，这些谓词要么是可生成的，要么是Co-NP难的。

Keyword:

L systems

Promise problems

0Lness problem

Undecidability

Productiveness

Computational complexity