Probabilistic Tree Automata
Probabilistic Tree Automata
复制标题
概率树自动机
DOI：
10.1145/800161.805165
复制
发表时间：
1970
期刊：
影响因子：
--
通讯作者：
C. Ellis
中科院分区：
文献类型：
--
作者：
C. Ellis
本文的目的有三个方面。首先，它将向读者介绍概率语言和概率语法的概念。其次，它表明以前的概率有限自动机的定义总是局限于8类自动机中的1类，并表明其他类是有用的。第三，将概率概念从有限自动机扩展到更高层次的自动机（如概率pda和概率图灵自动机）。给出了该理论在概率树自动机开发中的具体应用。给出了有关这些自动机的定理及其操作。指出这种类型的自动机是相关的，因为它具有概率上下文无关语言的特征。结果摘自作者的博士论文
The purpose of this paper is meant to be three-fold. First it will introduce the reader to the concepts of Probabilistic Languages and Probabilistic Grammars. Second, it indicates that previous definitions of probabilistic finite automaton have always been restricted to 1 of 8 classes of automaton and shows that other classes are useful. Third, the probabilistic concept is extended from finite automata to higher level automata (such as probabilistic PDAs and probabilistic Turing automata). A specific application of this theory is given in the development of Probabilistic Tree Automata. Theorems concerning these automata and operations on them are presented. It is indicated that this type of automaton is relevant because it characterizes Probabilistic Context Free Languages. The results are taken from the author's PhD Thesis.4