On splitting recursive sets

DOI10.1016/0022-0000(78)90034-XzbMath0392.03028OpenAlexW2078845413MaRDI QIDQ1251652

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

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

Related Items (8)

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

Cites Work

• Splitting a context-sensitive set
• On the Structure of Polynomial Time Reducibility
• On the Computational Complexity of Algorithms
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On splitting recursive sets