Partially-commutative context-free languages
Partially-commutative context-free languages
复制标题
部分交换上下文无关语言
DOI：
10.4204/eptcs.89.4
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
S. Lasota
中科院分区：
文献类型：
--
作者：
Wojciech Czerwinski;S. Lasota
本文是关于一类扩展上下文无关语言（CFL）的语言，并且在shuffle下是稳定的。具体来说，我们调查类的部分交换上下文无关语言（PCCFL），其中非终端符号是可交换的，根据一个二元独立关系，非常像在迹理论。该类最近已被提出作为一个强大的类，包括CFL和交换CFL。本文综述了PCCFL的性能。我们确定了一个自然对应的自动机模型：无状态多下推自动机。我们证明了自然操作下的类的稳定性，包括同态图像和洗牌。最后，我们与PCCFL的表现力其他两个相关的类：CFL扩展洗牌和跟踪关闭的CFL。在技术贡献的文件是泵引理，作为一个优雅的完成已知的泵性能的正规语言，CFL和交换CFL。
The paper is about a class of languages that extends context-free languages (CFL) and is stable under shuffle. Specifically, we investigate the class of partially-commutative context-free languages (PCCFL), where non-terminal symbols are commutative according to a binary independence relation, very much like in trace theory. The class has been recently proposed as a robust class subsuming CFL and commutative CFL. This paper surveys properties of PCCFL. We identify a natural corresponding automaton model: stateless multi-pushdown automata. We show stability of the class under natural operations, including homomorphic images and shuffle. Finally, we relate expressiveness of PCCFL to two other relevant classes: CFL extended with shuffle and trace-closures of CFL. Among technical contributions of the paper are pumping lemmas, as an elegant completion of known pumping properties of regular languages, CFL and commutative CFL.