scientific article; zbMATH DE number 3876594
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}\).
- Remarks on graph complexity. (Extended abstract)
- On a certain complexity estimate in graph theory
- Complexity of computation of some functions of graphs
- scientific article; zbMATH DE number 706829
- On Graph Complexity
- Computational complexity of graphs
- The complexity of finite graphs
- scientific article; zbMATH DE number 7300406
- Computational complexity of the graph approximation problem
- The complexity of graph problems for succinctly represented graphs
- A bound for the complexity of a simple graph
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- On the computational complexity of graph closures
- Graph complexity and slice functions
- A computational complexity comparative study of graph tessellation problems
- On the typical case complexity of graph optimization
- On the complexity of computing the excessive \([B]\)-index of a graph
- Complexity aspects of the computation of the rank of a graph
- scientific article; zbMATH DE number 3874608 (Why is no real title available?)
- scientific article; zbMATH DE number 5527901 (Why is no real title available?)
- The complexity of graph problems for succinctly represented graphs
- scientific article; zbMATH DE number 3997177 (Why is no real title available?)
- On the complexity of some problems related to graph extensions
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)