scientific article

Publication date: 1986

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

upper bounds automata simulations lower bounds formal languages relativization complexity measures complexity classes determinism versus nondeterminism reducibilities time 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 (54)

The polynomially exponential time restrained analytical hierarchy ⋮ Classification of the index sets of low \([n^ p\) and high \([n]^ p\)] ⋮ The complexity of combinatorial problems with succinct input representation ⋮ Reversal-bounded nondeterministic multicounter machines and complementation ⋮ The equivalence of pebbles and sensing heads for finite automata ⋮ ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA ⋮ The complexity of PDL with interleaving ⋮ Some observations on the connection between counting and recursion ⋮ The problem of space invariance for sequential machines ⋮ On reversal bounded alternating Turing machines ⋮ More complicated questions about maxima and minima, and some closures of NP ⋮ Recursion theoretic characterizations of complexity classes of counting functions ⋮ Tradeoffs for language recognition on alternating machines ⋮ Constructions for alternating finite automata^∗ ⋮ On the complexity of graph reconstruction ⋮ Some modifications of auxiliary pushdown automata ⋮ Unambiguous computations and locally definable acceptance types ⋮ Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n)) ⋮ On the equivalence of distributed systems with queries and communication ⋮ Weak parallel machines: A new class of physically feasible parallel machine models ⋮ The code problem for traces -- improving the boundaries ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Tree-walking-storage automata ⋮ Unnamed Item ⋮ Boundary sets of regular and context-free languages ⋮ On the expressive power of the shuffle operator matched with intersection by regular sets ⋮ Once-Marking and Always-Marking 1-Limited Automata ⋮ SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS ⋮ On the computational complexity of problems related to distinguishability sets ⋮ Descriptional complexity of limited automata ⋮ REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS ⋮ Reversal complexity revisited ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ An NP-complete language accepted in linear time by a one-tape Turing machine ⋮ Iterated stack automata and complexity classes ⋮ On quasilinear-time complexity theory ⋮ On complexity of grammars related to the safety problem ⋮ A survey of space complexity ⋮ Bounded linear logic: A modular approach to polynomial-time computability ⋮ Unambiguity of circuits ⋮ Linear-time limited automata ⋮ On the descriptional complexity of Watson-Crick automata ⋮ Limited automata and unary languages ⋮ A Note on a Tree-Based 2D Indexing ⋮ The power of two-way deterministic checking stack automata ⋮ Sorting, linear time and the satisfiability problem ⋮ Language complexity of rotations and Sturmian sequences ⋮ The ancestor width of grammars and languages ⋮ Realtime subshifts ⋮ Nondeterministic multicounter machines and complementation ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata ⋮ Deterministic Turing machines in the range between real-time and linear-time. ⋮ A time lower bound for satisfiability ⋮ Limiting characterizations of low level space complexity classes

This page was built for publication: