On path equivalence of nondeterministic finite automata

doi:10.1016/0020-0190(96)00039-7

完整後設資料紀錄

DC 欄位	值	語言
dc.contributor.author	Tzeng, WG	en_US
dc.date.accessioned	2014-12-08T15:02:43Z	-
dc.date.available	2014-12-08T15:02:43Z	-
dc.date.issued	1996-04-08	en_US
dc.identifier.issn	0020-0190	en_US
dc.identifier.uri	http://dx.doi.org/10.1016/0020-0190(96)00039-7	en_US
dc.identifier.uri	http://hdl.handle.net/11536/1350	-
dc.description.abstract	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.	en_US
dc.language.iso	en_US	en_US
dc.subject	algorithms	en_US
dc.subject	computational complexity	en_US
dc.subject	path equivalence	en_US
dc.subject	automaton	en_US
dc.title	On path equivalence of nondeterministic finite automata	en_US
dc.type	Article	en_US
dc.identifier.doi	10.1016/0020-0190(96)00039-7	en_US
dc.identifier.journal	INFORMATION PROCESSING LETTERS	en_US
dc.citation.volume	58	en_US
dc.citation.issue	1	en_US
dc.citation.spage	43	en_US
dc.citation.epage	46	en_US
dc.contributor.department	交大名義發表	zh_TW
dc.contributor.department	資訊工程學系	zh_TW
dc.contributor.department	National Chiao Tung University	en_US
dc.contributor.department	Department of Computer Science	en_US
dc.identifier.wosnumber	WOS:A1996UP89100009	-
dc.citation.woscount	4	-
顯示於類別：	期刊論文

文件中的檔案：

A1996UP89100009.pdf

若為 zip 檔案，請下載檔案解壓縮後，用瀏覽器開啟資料夾中的 index.html 瀏覽全文。