Skip to main navigation Skip to search Skip to main content

Complexity of sufficient-completeness

  • General Electric
  • Rensselaer Polytechnic Institute

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

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.

Original languageEnglish
Title of host publicationFoundations of Software Technology and Theoretical Computer Science - 6th Conference, Proceeding
EditorsKesav V. Nori
PublisherSpringer Verlag
Pages426-442
Number of pages17
ISBN (Print)9783540171799
DOIs
StatePublished - 1986
Event6th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1986 - New Delhi, India
Duration: Dec 18 1986 → Dec 20 1986

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume241 LNCS

Conference

Conference6th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1986
Country/TerritoryIndia
CityNew Delhi
Period12/18/86 → 12/20/86

Keywords

  • Normal forms
  • PSPACE
  • Sufficient-completeness
  • Term rewriting systems

Fingerprint

Dive into the research topics of 'Complexity of sufficient-completeness'. Together they form a unique fingerprint.

Cite this