Propositional Tree Automata
Propositional Tree Automata
复制标题
命题树自动机
DOI：
10.1007/11805618_5
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Mahesh Viswanathan
中科院分区：
文献类型：
--
作者：
Joe Hendrix;H. Ohsaki;Mahesh Viswanathan
在本文中，我们引入了一个新的树自动机框架，称为命题树自动机，捕捉类的树语言，是封闭的方程理论和布尔运算。这个框架起源于开发一个充分的完整性检查规范重写模方程理论的工作。命题树自动机识别正则方程树语言。然而，与正则方程树自动机不同，命题树自动机类在布尔运算下是封闭的。这种额外的表现力并不影响成员问题的可判定性。本文还用结合理论详细分析了命题树自动机的空性问题。虽然不可判定的一般，我们提出了一个半算法检查空的机器学习的基础上，我们发现在实践中很有用。
In the paper, we introduce a new tree automata framework, called propositional tree automata, capturing the class of tree languages that are closed under an equational theory and Boolean operations. This framework originates in work on developing a sufficient completeness checker for specifications with rewriting modulo an equational theory. Propositional tree automata recognize regular equational tree languages. However, unlike regular equational tree automata, the class of propositional tree automata is closed under Boolean operations. This extra expressiveness does not affect the decidability of the membership problem. This paper also analyzes in detail the emptiness problem for propositional tree automata with associative theories. Though undecidable in general, we present a semi-algorithm for checking emptiness based on machine learning that we have found useful in practice.
使用树自动机进行 XML 访问控制的静态分析
DOI：
--
发表时间：
2006
期刊：
Computer Software (to appear)
影响因子：
--
作者：
Isao Yagi;et al.
通讯作者：
et al.