@article{HUYNH1985103,
    Abstract = {In this paper we investigate the computational complexity of the inequivalence problems for commutative grammars. We show that the inequivalence problems for type 0 and context-sensitive commutative grammars are undecidable whereas decidability in nondeterministic exponential-time holds for the classes of regular and context-free commutative grammars. For the latter the inequivalence problems are Σp2-hard.},
    Author = {Huynh, Dung T.},
    File = {The complexity of equivalence problems for commutative grammars - Huynh (0) (0) - a - a - x.pdf},
    ISSN = {0019-9958},
    Journal = {Information and Control},
    Number = {1},
    Pages = {103 - 121},
    Title = {The complexity of equivalence problems for commutative grammars},
    URL = {http://www.sciencedirect.com/science/article/pii/S0019995885800152},
    Volume = {66},
    Year = {1985},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0019995885800152},
    bdsk-url-2 = {http://dx.doi.org/10.1016/S0019-9958(85)80015-2},
    date-added = {2016-01-25 10:35:01 +0000},
    date-modified = {2016-01-25 10:35:01 +0000},
    doi = {10.1016/S0019-9958(85)80015-2}
}

@article{HUYNH1985103, Abstract = {In this paper we investigate the computational complexity of the inequivalence problems for commutative grammars. We show that the inequivalence problems for type 0 and context-sensitive commutative grammars are undecidable whereas decidability in nondeterministic exponential-time holds for the classes of regular and context-free commutative grammars. For the latter the inequivalence problems are Σp2-hard.}, Author = {Huynh, Dung T.}, File = {The complexity of equivalence problems for commutative grammars - Huynh (0) (0) - a - a - x.pdf}, ISSN = {0019-9958}, Journal = {Information and Control}, Number = {1}, Pages = {103 - 121}, Title = {The complexity of equivalence problems for commutative grammars}, URL = {http://www.sciencedirect.com/science/article/pii/S0019995885800152}, Volume = {66}, Year = {1985}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0019995885800152}, bdsk-url-2 = {http://dx.doi.org/10.1016/S0019-9958(85)80015-2}, date-added = {2016-01-25 10:35:01 +0000}, date-modified = {2016-01-25 10:35:01 +0000}, doi = {10.1016/S0019-9958(85)80015-2} }