Monodic Tree Kleene Algebra
Monodic Tree Kleene Algebra
复制标题
单一树克林代数
DOI：
10.1007/11828563_27
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
H. Furusawa
中科院分区：
文献类型：
--
作者：
Toshinori Takai;H. Furusawa
我们提出了一个正则树语言的准等式的声音公理化，称为单次树Kleene代数。该代数弱于Kozen引入的Kleene代数。我们发现了正则树语言的一个子类，对于这个子类，单次树Kleene代数是完备的。虽然正则树表达式可以有两种或多种占位符，但子类只能配备其中一种。沿着Kozen的原始证明，我们证明了基于单次树Kleene代数上矩阵表示的树自动机的确定性和最小化的完备性定理。
We propose a quasi-equational sound axiomatization of regular tree languages, called monodic tree Kleene algebra. The algebra is weaker than Kleene algebra introduced by Kozen. We find a subclass of regular tree languages, for which monodic tree Kleene algebra is complete. While regular tree expressions may have two or more kinds of place holders, the subclass can be equipped with only one kind of them. Along the lines of the original proof by Kozen, we prove the completeness theorem based on determinization and minimization of tree automata represented by matrices on monodic tree Kleene algebra.