Robustness and closure properties of recognizable languages in adhesive categories
Robustness and closure properties of recognizable languages in adhesive categories
复制标题
粘合剂类别中可识别语言的鲁棒性和封闭性
DOI：
10.1016/j.scico.2014.08.006
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sebastian Küpper
中科院分区：
文献类型：
--
作者：
H.J. Sander Bruggink;Barbara König;Sebastian Küpper
本文研究了由自动机函子定义的粘着范畴中的余span的可识别语言，其中可识别的图语言是一个特例.本文的贡献有三：首先，我们证明了可识别语言的概念是鲁棒的，在这个意义上，半函子，即，不一定保持身份的函子表征可识别的语言。这是通过转换半函子函子的一个过程类似于消除非确定性有限automata.Second，依靠这个结果，我们表明，可识别的语言是封闭的级联下，即根据cosspan组成，通过提供一个具体的建设，创建一个级联自动机从两个给定的自动机。该构造比有限自动机的相应构造复杂得多。最后给出了Kleene星星和代换的负闭包性质。
We consider recognizable languages of cospans in adhesive categories defined via automaton functors, of which recognizable graph languages are a special case.There are three contributions in this paper: we first show that the notion of recognizable languages is robust in the sense that also semi-functors, i.e., functors that do not necessarily preserve identities, characterize recognizable languages. This is done by converting semi-functors to functors with a procedure akin to epsilon elimination for non-deterministic finite automata.Second, relying on this result, we show that recognizable languages are closed under concatenation, i.e. under cospan composition, by providing a concrete construction that creates a concatenation automaton from two given automata. The construction is considerably more complex than the corresponding construction for finite automata. We conclude by showing negative closure properties for Kleene star and substitution.
登录
查看更多内容
影响因子：
0.7
作者：
P. Baldan;F. Bonchi;A. Corradini;T. Heindel;B. König
通讯作者：
B. König
Hyperedge 替换：语法和语言
DOI：
--
发表时间：
1992
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
A. Habel
通讯作者：
A. Habel
影响因子：
1
作者：
COURCELLE, B
通讯作者：
COURCELLE, B
匹配限制字符串重写系统
DOI：
--
发表时间：
2003
期刊：
Applicable Algebra in Engineering, Communication and Computing
影响因子：
--
作者：
Alfons Geser;D. Hofbauer;Johannes Waldmann
通讯作者：
Johannes Waldmann
可交换正则语言
DOI：
--
发表时间：
1991
期刊：
SIGA
影响因子：
--
作者：
C. P. Rupert
通讯作者：
C. P. Rupert