The recursion-theoretic structure of complexity classes
type: Item
instance of: scholarly article
title: The recursion-theoretic structure of complexity classes
zbMATH Open document ID: 0576.03025
DOI: 10.1016/0304-3975(85)90217-8
author: Diana Schmidt
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: Let A be any language. A is said to be a gap language if A is the union of the maximal subsets of A of the form \(\{\) \(w| m\leq | w| \leq n\}\) (m\(\leq n\in N)\) (intervals of A). The gaps of A are the intervals of \(\bar A.\) A class \({\mathbb{C}}\) of languages is said to be recursively gap closed if for every recursive gap language \(G_ 0\) with infinitely many gaps and intervals, there is a language \(G\in {\mathbb{C}}\) such that \(\bar G\in {\mathbb{C}}\) and \(G_ 0\) contains infinitely many intervals belonging to G as well as gaps belonging to \(\bar G.\) A class of sets \({\mathbb{C}}\) is recursively presentable if there is an effective sequence \(M_ i\) of total Turing machines such that \({\mathbb{C}}=\{L(M_ i)|\) \(i\in N\}.\) The author shos that if \({\mathbb{C}}\) is a class of recursive languages which is recursive gap closed and closed under union and intersection, and \({\mathbb{C}}_ 1\), \({\mathbb{C}}_ 2\) are recursively presentable classes which are closed under finite variations then \({\mathbb{C}}\subseteq {\mathbb{C}}_ 1\cup {\mathbb{C}}_ 2\Rightarrow {\mathbb{C}}\subseteq C_ 1\) or \({\mathbb{C}}\subseteq {\mathbb{C}}_ 2\); and \({\mathbb{C}}={\mathbb{C}}_ 1\cup {\mathbb{C}}_ 2\Rightarrow {\mathbb{C}}={\mathbb{C}}_ 1\) or \({\mathbb{C}}={\mathbb{C}}_ 2.\) The article contains a series of results closely related to the one just mentioned. The complexity classes DTIME(n), DSPACE\(_{on-line}(\log n)\), the class of context-sensitive languages are shown to be recursively gap closed. The class of context-free languages and hence also that of regular languages, is not recursively gap closed. The article contains a number of other results.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3920454
zbMATH Keywords: gap language
zbMATH Keywords: recursive languages
zbMATH Keywords: recursively presentable classes
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90217-8
OpenAlex ID: W2066107173
cites work: Q5183082
cites work: On splitting recursive sets
cites work: A note on structure and looking back applied to the relative complexity of computable functions
cites work: Space bounds for processing contentless inputs
cites work: Some Results on Tape-Bounded Turing Machines
cites work: On the Structure of Polynomial Time Reducibility
cites work: A comparison of polynomial time reducibilities
cites work: On the structure of sets in NP and other complexity classes
cites work: Q5180413
cites work: Strong nondeterministic polynomial-time reducibilities
cites work: Q3312209
cites work: A uniform approach to obtain diagonal sets in complexity classes
cites work: Q3344189
cites work: Q5636862
description: scientific article; zbMATH DE number 3920454