@inproceedings{32ff6d54402d4c5cb482cbf5217283be,
title = "Complexity of sufficient-completeness",
abstract = "The sufficient-completeness property of equational specifications has been found useful in providing guidelines for abstract data type specifications as well as in proving inductive properties using the inductionless-induction method. The sufficient-completeness property is known to be undecidable in general. In an earlier paper, it was shown to be decidable for constructor-preserving, complete (canonical) term rewriting systems, even when there are relations between constructors. The complexity of the sufficient-completeness property under certain conditions is discussed. It is shown that the sufficient-completeness problem for term rewriting systems without any relations on constructors is co-NP-complete. However, the problem is PSPACE-hard even for linear constructor-preserving term rewriting systems when relations on constructors are allowed.",
keywords = "Normal forms, PSPACE, Sufficient-completeness, Term rewriting systems",
author = "Deepak Kapur and Paliath Narendran and Hantao Zhang",
note = "Publisher Copyright: {\textcopyright} 1986, Springer Verlag. All rights reserved.; 6th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1986 ; Conference date: 18-12-1986 Through 20-12-1986",
year = "1986",
doi = "10.1007/3-540-17179-7\_26",
language = "English",
isbn = "9783540171799",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "426--442",
editor = "Nori, \{Kesav V.\}",
booktitle = "Foundations of Software Technology and Theoretical Computer Science - 6th Conference, Proceeding",
}