树自动机超最小化  

Hyper-Minimization for Tree Automaton

作　　者：胡芙 黄兆华[1] 

机构地区：[1]华东交通大学软件学院,南昌330013

出　　处：《南昌航空大学学报（自然科学版）》2015年第2期27-32,共6页Journal of Nanchang Hangkong University(Natural Sciences)

基　　金：江西省自然科学基金(20122BAB201040);江西省教育厅科技项目(GJJ13337)

摘　　要：提出一种新的树自动机超最小化算法,该算法将确定的树自动机转换为确定的有限自动机,再根据确定的有限自动机划分f-等价类方法及状态合并算法,对转换后的自动机进行超最小化,得到最终具有有限差异的确定的树自动机。通过采用实例算法证实:该算法与现有的确定的树自动机超最小化算法相比,具有过程简单、效率高等优点,是一种高效易用的算法。A new hyper-minimization algorithm of tree automaton was proposed in this paper. The deterministic tree automaton was transformed into deterministic finite automaton, then according to partitioned states into f-equivalence class and merged f-equivalence states algorithm of deterministic finite automaton, used hyper-minimization to the transformed automaton, got the final tree automaton which has finite differences. Compared with the exist algorithm, this algorithm is more simple and effectively, so it is an effective and easy-used algorithm.

关 键 词：树自动机 超最小化 f-等价类 

分 类 号：TB311[一般工业技术—材料科学与工程]