A note on complete sets and transitive closure

DOI10.1007/BF01786987MaRDI QIDQ3959428zbMATH OpenOpenAlexFDO

Authors 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

length-preserving relationNP-completePSPACE-complete

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(1)

• On some natural complete operators

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3959428)