Abstract
In this paper we shall characterize the computational complexity of two decision problems: the inequality problem and the uniform word problem for semilinear sets. It will be proved that the first problem is log-complete in the second class (Σp 2) of the polynomial-time hierarchy and the second problem is log-complete in NP. Moreover we shall show that these problems restricted to the 1-dimensional case have the ‘same’ computational complexity as the general case.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E.Cardoza, R.Lipton and A.R.Meyer: "Exponential Space Complete Problem for Petri Nets and Commutative Semigroups", in "Proc. of the 8-th Annual ACM Symposium on the Theory of Computing" (1976), pp. 50–54.
S.Eilenberg and M.P.Schützenberger: "Rational Sets in Commutative Monoids", Journal of Algebra, No 13, 1969, pp. 173–191.
J. Von Zur Gathen and M. Sieveking: "A bound on Solutions of Linear Integer Equalities and Inequalities", Proc. of the AMS, Vol. 72, No 1, 1978, pp. 155–158.
M. Gerstenhaber: "Theory of Convex Polyhedral Cones", in Proc. of a Conference on "Activity Analysis of Production and Allocation", Ed. T.C. Koopmans, John Willey & Sons — Chapman & Hall, 1951.
S.Ginsburg: "The Mathematical Theory of Context-free Languages", Mc Graw-Hill, 1966.
F. Glover and R.E.D. Woolsey: "Aggregating Diophantine Equations", Zeitschrift für Operations Researchs, Vol. 16, 1972, pp. 1–10.
G.Hotz: "Eine Neue Invariante Kontext-freier Grammatiken", 1978, to appear in Theoretical Computer Science.
G.Hotz: "Verschränkte Homomorphismen Formaler Sprachen", 1979, to appear in RAIRO.
W.J.Paul: "Komplexitätstheorie", Teubner Verlag, 1979.
L.Stockmeyer and A.R.Meyer: "Word Problem Requiring Exponential Time", in Proc. of the 5-th Annual Symposium on the Theory of Computing, 1973, pp. 1–9.
L. Stockmeyer: "The Polynomial-Time Hierarchy", Theoretical Computer Science, Vol. 3, 1977, pp. 1–12.
J.Stoer and C.Witzgall: "Convexity and Optimization in Finite Dimension I", Springer Verlag, 1970.
C. Wrathall: "Complete Sets and the Polynomial-Time Hierarchy", Theoretical Computer Science, Vol. 3, 1977, pp. 23–33.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1980 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huynh, TD. (1980). The complexity of semilinear sets. In: de Bakker, J., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 1980. Lecture Notes in Computer Science, vol 85. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10003-2_81
Download citation
DOI: https://doi.org/10.1007/3-540-10003-2_81
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-10003-4
Online ISBN: 978-3-540-39346-7
eBook Packages: Springer Book Archive