Search for Author All Reviews
	Huynh, Dung     Options: All Media Types Journals Proceedings Div Books Whole Books Other Date Reviewed Title Author Publisher Published Date Descending Ascending Date Reviewed     1 - 4 of 4 reviews       Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states Howell R., Rosier L., Huynh D., Yen H. Theoretical Computer Science 46(2-3): 107-140, 1986.  Type: Article This paper establishes the basic complexity results relating to two special cases of vector addition systems with states (VASS), namely, finite VASS and two-dimensional VASS. In the case of finite VASS, using a new approach based on th...... Aug 1 1988     Complexity of the word problem for commutative semigroups of fixed dimension Huynh D. Acta Informatica 22(4): 421-432, 1985.  Type: Article It is proved that the uniform word problem for commutative semigroups of dimension k (shortly, UWP(k)) is complete for the symmetric linear space in the case of k≥; UWP(1) is solvable in polynomial time. Als...... May 1 1986     Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is &Sgr;p-2--complete Huynh D. Theoretical Computer Science 33(2-3): 305-326, 1984.  Type: Article It is well known that any context-free grammar over a one-letter alphabet generates a regular language. The proof of this result is constructive; however, its complexity is exponential. The present paper investigates the complexity of ...... Jul 1 1985     Commutative grammars: the complexity of uniform word problems Huynh D. Information and Control 57(1): 21-39, 1983.  Type: Article Commutative grammars considering free commutative monoids are introduced. One of the nice features of the paper is that the complexity of the uniform word problem for context-free grammars is discussed utiizing induced context-free gr...... Feb 1 1985
	Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud® Terms of Use | Privacy Policy