A note on complete sets and transitive closure

DOI10.1007/BF01786987zbMath0495.68039OpenAlexW2045473234MaRDI QIDQ3959428

Ronald V. Book, Celia Wrathall

Publication date: 1982

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01786987

zbMATH Keywords

NP-completePSPACE-completelength-preserving relation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (1)

On some natural complete operators

Cites Work

• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Polynomial Space and Transitive Closure
• Classes of automata and transitive closure
• The complexity of theorem-proving procedures

This page was built for publication: A note on complete sets and transitive closure