標題: On path equivalence of nondeterministic finite automata
作者: Tzeng, WG
交大名義發表
資訊工程學系
National Chiao Tung University
Department of Computer Science
關鍵字: algorithms;computational complexity;path equivalence;automaton
公開日期: 8-四月-1996
摘要: Two nondeterministic finite automata (NFAs) are said to be path equivalent if each string is accepted by the two automata via the same number of computation paths. In this paper we show the following. (1) The path equivalence problem for NFAs without lambda-cycles is solvable not only in polynomial sequential time but also in O(log(2)(n)) parallel time using a polynomial number of processors, where n is the total number of states in two NFAs. (2) The path equivalence problem for NFAs with lambda-cycles is PSPACE-complete, hence decidable.
URI: http://dx.doi.org/10.1016/0020-0190(96)00039-7
http://hdl.handle.net/11536/1350
ISSN: 0020-0190
DOI: 10.1016/0020-0190(96)00039-7
期刊: INFORMATION PROCESSING LETTERS
Volume: 58
Issue: 1
起始頁: 43
結束頁: 46
顯示於類別:期刊論文


文件中的檔案:

  1. A1996UP89100009.pdf