scientific article

zbMath0584.68062MaRDI QIDQ3707408

Gerd Wechsung, Klaus W. Wagner

Publication date: 1986

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

automatasimulationsformal languagescomplexity measurescomplexity classesLower boundsdeterminism versus nondeterminismRelativizationUpper boundsreducibilitiestime versus space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (26)

A linear-time simulation of deterministic \(d\)-limited automata ⋮ Refined simulation of multihead automata ⋮ Weak and strong one-way space complexity classes ⋮ Prediction of infinite words with automata ⋮ Deterministic Stack Transducers ⋮ A time-space hierarchy between polynomial time and polynomial space ⋮ Performing regular operations with 1-limited automata ⋮ Space measures for storage modification machines ⋮ Reversals and alternation ⋮ On weak growing context-sensitive grammars ⋮ The emptiness problem for intersections of regular languages ⋮ Unnamed Item ⋮ Computation models and function algebras ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ On universally easy classes for NP-complete problems. ⋮ Two-way machines and de Bruijn words ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ On the Computational Capacity of Parallel Communicating Finite Automata ⋮ Knapsack problems for NL ⋮ Alternation in simple devices ⋮ Linear speed-up does not hold on Turing machines with tree storages ⋮ Reversible parallel communicating finite automata systems ⋮ On the decidability of finding a positive ILP-instance in a regular set of ILP-instances ⋮ Converting nondeterministic two-way automata into small deterministic linear-time machines ⋮ Notes on looping deterministic two-way pushdown automata ⋮ Searching for applicable versions of computable structures

This page was built for publication: