On the complexity of Bounded Second-Order Unification and Stratified Context Unification
- 5 May 2010
- journal article
- Published by Oxford University Press (OUP) in Logic Journal of the IGPL
- Vol. 19 (6) , 763-789
Abstract
Bounded Second-Order Unification is a decidable variant of undecidable Second-Order Unification. Stratified Context Unification is a decidable restriction of Context Unification, whose decidability is a long-standing open problem. This paper is a join of two separate previous, preliminary papers on NP-completeness of Bounded Second-Order Unification and Stratified Context Unification. It clarifies some omissions in these papers, joins the algorithmic parts that construct a minimal solution, and gives a clear account of a method of using singleton tree grammars for compression that may have potential usage for other algorithmic questions in related areas.Keywords
This publication has 13 references indexed in Scilit:
- The Complexity of Monadic Second-Order UnificationSIAM Journal on Computing, 2008
- Word Problems and Membership Problems on Compressed WordsSIAM Journal on Computing, 2006
- On the Undecidability of Second-Order UnificationInformation and Computation, 2000
- On rewrite constraints and context unificationInformation Processing Letters, 2000
- Complexity of Makanin's algorithmJournal of the ACM, 1996
- A unification algorithm for second-order monadic termsAnnals of Pure and Applied Logic, 1988
- The undecidability of the second-order unification problemTheoretical Computer Science, 1981
- IO and OI. IIJournal of Computer and System Sciences, 1978
- IO and OI. IJournal of Computer and System Sciences, 1977
- THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUPMathematics of the USSR-Sbornik, 1977