On splitting recursive sets

DOI10.1016/0022-0000(78)90034-XMaRDI QIDQ1251652zbMATH OpenOpenAlexFDO

Authors Seth Breidbart

Publication date 1978

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(78)90034-x

zbMATH Keywords

Blum MeasuresComputational ComplexityContext-Free SetDeterministic Turing MachineFormal LanguageRecursively Enumerable SetsRegular SetSplitting Recursive Sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• On the Computational Complexity of Algorithms
• On the Structure of Polynomial Time Reducibility
• Splitting a context-sensitive set

Cited in

(8)

• The recursion-theoretic structure of complexity classes
• Diagonalization, uniformity, and fixed-point theorems
• On the lattices of NP-subspaces of a polynomial time vector space over a finite field
• Bi-immune sets for complexity classes
• OnP-subset structures
• A short note on simultaneous splitting
• Oracle-dependent properties of the lattice of NP sets
• Complexity-theoretic algebra. II: Boolean algebras

This page was built for publication: On splitting recursive sets

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