No label defined (Q3341898)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3876594
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3876594 |
Statements
1982
0 references
complexity
0 references
Turing machine
0 references
context sensitive language
0 references
closure properties
0 references
0.95376766
0 references
0.93779707
0 references
0.93337876
0 references
0 references
0 references
0.91218156
0 references
Let \(\Sigma\) be a finite set. A partial function \(f:(\Sigma^*)^ r\to (\Sigma^*)^ s\) is computed by an off-line deterministic Turing machine if, when started with \(\#x_ 1\#...\#x_ r\#\) on its input tape, the machine halts in an accepting state with \(\#y_ 1\#...\#y_ s\#\) on its output tape whenever \(f(x_ 1,...,x_ r)=(y_ 1,...,y_ s)\) and halts in a non-accepting state if \((x_ 1,...,x_ r)\) is not in dom(f). Let \({\mathcal D}\) be the collection of such functions f which can be computed within a space bound S, for some space-constructible function S satisfying \(S(n)\geq\log_ 2 n,\) and such that for \(x\in dom(f)\) the space used to compute f(x) is bounded by \(c\cdot\max (length(x),\quad length(f(x)))\) for some constant c. Theorem: If \(f\in {\mathcal D}\), then the graph of f, \(L_ f=\{\#x_ 1\#...\#x_ r\#y_ 1\#...\#y_ s\#:f(x_ 1,...,x_ r)=(y_ 1,...,y_ s)\},\) is a deterministic context sensitive language. This gives a means of constructing context sensitive languages whose complements are also context sensitive. The paper goes on to prove a number of closure properties of the class \({\mathcal D}\) under various operations, leading to the result: Every computable function is the composition of two functions in \({\mathcal D}\).
0 references