@article{Tzeng:IPL:1996,
    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.(1) The path equivalence problem for NFAs without {$\lambda$}-cycles is solvable not only in polynomial sequential time but also in O(log2(n)) parallel time using a polynomial number of processors, where n is the total number of states in two NFAs.2.(2) The path equivalence problem for NFAs with {$\lambda$}-cycles is PSPACE-complete, hence decidable.},
    Author = {Tzeng, Wen-Guey},
    File = {On path equivalence of nondeterministic finite automata - wen-guey1996 - a - a - a - x.pdf},
    ISSN = {0020-0190},
    Journal = {Information Processing Letters},
    Keywords = {Algorithms, Computational complexity, Path equivalence, Automaton},
    Number = {1},
    Pages = {43--46},
    Title = {On path equivalence of nondeterministic finite automata},
    URL = {http://www.sciencedirect.com/science/article/pii/0020019096000397},
    Volume = {58},
    Year = {1996},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/0020019096000397},
    bdsk-url-2 = {https://doi.org/10.1016/0020-0190(96)00039-7},
    date-added = {2020-02-07 18:48:24 +0100},
    date-modified = {2023-07-26 21:33:21 +0200},
    doi = {10.1016/0020-0190(96)00039-7}
}

@article{Tzeng:IPL:1996, 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.(1) The path equivalence problem for NFAs without {$\lambda$}-cycles is solvable not only in polynomial sequential time but also in O(log2(n)) parallel time using a polynomial number of processors, where n is the total number of states in two NFAs.2.(2) The path equivalence problem for NFAs with {$\lambda$}-cycles is PSPACE-complete, hence decidable.}, Author = {Tzeng, Wen-Guey}, File = {On path equivalence of nondeterministic finite automata - wen-guey1996 - a - a - a - x.pdf}, ISSN = {0020-0190}, Journal = {Information Processing Letters}, Keywords = {Algorithms, Computational complexity, Path equivalence, Automaton}, Number = {1}, Pages = {43--46}, Title = {On path equivalence of nondeterministic finite automata}, URL = {http://www.sciencedirect.com/science/article/pii/0020019096000397}, Volume = {58}, Year = {1996}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/0020019096000397}, bdsk-url-2 = {https://doi.org/10.1016/0020-0190(96)00039-7}, date-added = {2020-02-07 18:48:24 +0100}, date-modified = {2023-07-26 21:33:21 +0200}, doi = {10.1016/0020-0190(96)00039-7} }