1. You are Here：

Full metadata record
DC FieldValueLanguage
dc.contributor.authorTzeng, WGen_US
dc.date.accessioned2014-12-08T15:02:43Z-
dc.date.available2014-12-08T15:02:43Z-
dc.date.issued1996-04-08en_US
dc.identifier.issn0020-0190en_US
dc.identifier.urihttp://dx.doi.org/10.1016/0020-0190(96)00039-7en_US
dc.identifier.urihttp://hdl.handle.net/11536/1350-
dc.description.abstractTwo 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.isoen_USen_US
dc.subjectalgorithmsen_US
dc.subjectcomputational complexityen_US
dc.subjectpath equivalenceen_US
dc.subjectautomatonen_US
dc.titleOn path equivalence of nondeterministic finite automataen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/0020-0190(96)00039-7en_US
dc.identifier.journalINFORMATION PROCESSING LETTERSen_US
dc.citation.volume58en_US
dc.citation.issue1en_US
dc.citation.spage43en_US
dc.citation.epage46en_US
dc.contributor.department交大名義發表zh_TW
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentNational Chiao Tung Universityen_US
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:A1996UP89100009-
dc.citation.woscount4-
Appears in Collections:Articles


Files in This Item:

  1. A1996UP89100009.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.

Related Contents
Loading...