.png){kind=icon}
返回
Deterministic pushdown automata with translucent input letters ☆
.png){kind=icon}
OA
AI
DOI：10.1016/j.ic.2026.105403.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
透明输入字母的使用代表了在自动机中实现非连续输入处理的一种方式。具体来说，一个透明自动机对输入进行多次从左到右的扫描：根据当前状态，某些符号可见并可被处理，而另一些符号不可见，可能需要在另一次扫描中被处理。我们还区分了返回模式和非返回模式，它们在读取符号后的行为方式上有所不同：在返回模式下，新的扫描立即开始；而在非返回模式下，设备处理下一个可见符号。在此，我们研究了在返回模式和非返回模式下带有透明字母的确定下推自动机。我们证明非返回模式严格优于返回模式，并且这两种类型设备所接受的语言族可以严格排列在确定上下文无关语言和确定上下文敏感语言之间。此外，这两个语言族被证明与上下文无关语言、增长上下文敏感语言和Church-Rosser语言的语言族不可比较。接受非半线性语言的能力也得到了强调（解决了文献中的一个开放问题）。最后，我们研究了这两个语言族在布尔运算下的闭包性质，得出它们在补运算下是闭合的，但在并和交运算下不闭合。进一步的非闭包结果被指出适用于返回模式设备。
Keyword:
Translucent input letters
Deterministic pushdown automata
Returning and non-returning computations
Computational capacity
Closure properties
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
1
论文数:
79
被引数:
2.8K
机构
引用论文
.png){kind=icon}
Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata无状态确定性R(1)-自动机的确定性下推CD系统
PREAI
分享收藏Non-returning deterministic and nondeterministic finite automata with translucent letters无返回的确定性和非确定性有限自动机，带有半透明字母
PREAI
分享收藏On CD-systems of stateless deterministic R-automata with window size one无状态确定性R-自动机在窗口大小为1时的CD系统
PREAI
分享收藏The Church-Rosser languages are the deterministic variants of the growing context-sensitive languagesChurch-Rosser语言是增长性上下文敏感语言的确定型变体
PREAI
分享收藏
查看更多内容