scientific article; zbMATH DE number 3876594

From MaRDI portal
Publication:3341898





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}\).











This page was built for publication:

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