On the Computational Complexity of Algorithms

Cites work

scientific article; zbMATH DE number 3131080 (Why is no real title available?)
scientific article; zbMATH DE number 3201659 (Why is no real title available?)
scientific article; zbMATH DE number 3251431 (Why is no real title available?)
Classes of Predictably Computable Functions
On certain formal properties of grammars
Real time computation

Cited in

(only showing first 100 items - show all)

scientific article; zbMATH DE number 3417370 (Why is no real title available?)
Relative complexity of checking and evaluating
An introduction to tile-based self-assembly and a survey of recent results
Deterministic Turing machines in the range between real-time and linear-time.
Small universal accepting hybrid networks of evolutionary processors
Incremental delay enumeration: space and time
``V-tape, a virtual memory oriented data type, and its resource requirements
Linear-time simulation of multihead Turing machines
On the irrationality measure of the Thue-Morse constant
Komplexität von Algorithmen mit Anwendung auf die Analysis
On the Minimum Computation Time of Functions
Linear speed-up does not hold on Turing machines with tree storages
Speed-up theorems in type-2 computations using oracle Turing machines
Deterministic multitape automata computations
On transformations of programs
$\mathrm P \overset {?} {=} \mathrm{NP}$
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
Real-time computations with restricted nondeterminism
The complexity of total order structures
Computability and complexity in self-assembly
A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors
Hartmanis-Stearns Conjecture on Real Time and Transcendence
Complexity results for deciding networks of evolutionary processors
Counter machines and counter languages
Multi-stack-counter languages
Expressing computational complexity in constructive type theory
The developments of the concept of machine computability from 1936 to the 1960s
Tape-reversal bounded Turing machine computations
Deterministic real-time tree-walking-storage automata
Simulating two pushdown stores by one tape in $O(n^{1.5}\,\sqrt{\log \,n})$ time
Average case complexity theory
On time versus space. II
Characterizations of pushdown machines in terms of time-bounded computers
The 1982 ACM Turing Award lecture. An overview of computational complexity
Uniform tag sequences
On the possibility of basing cryptography on $\mathsf{EXP}\ne \mathsf{BPP} $
Time hierarchies for cryptographic function inversion with advice
Comparing complexity classes
The complexity of type inference for higher-order typed lambda calculi
A note on complexity measures for inductive classes in constructive type theory
Unary coded PSPACE-complete languages in $\mathrm{ASPACE}(\log\log n)$
Berechnungen in partiellen Algebren endlichen Typs
Writing stack acceptors
Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
Dimension and the structure of complexity classes
The complexity of two-player games of incomplete information
Reverse complexity
Multiplication, division, and shift instructions in parallel random access machines
Completeness proofs for propositional logic with polynomial-time connectives
Accepting networks of splicing processors: complexity results
Augmented loop languages and classes of computable functions
Real-time solutions of the origin-crossing problem
Palindrome recognition in real time by a multitape Turing machine
Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces
A complexity analysis of bisimilarity for value-passing processes
A unified approach to the definition of random sequences
Polynomial and abstract subrecursive classes
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
An application of the translational method
If the current clique algorithms are optimal, so is Valiant's parser
Fast on-line integer multiplication
Pushdown cellular automata
Sparse sets and collapse of complexity classes
Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
Implicit computation complexity in higher-order programming languages
Circuit lower bounds from NP-hardness of MCSP under turing reductions
Notes on Levin's theory of average-case complexity
On restricted turing computability
The theory of languages
Complexity barriers as independence
scientific article; zbMATH DE number 3644481 (Why is no real title available?)
Quasi-realtime languages
Lower bounds for multiplayer noncooperative games of incomplete information
On the computational complexity of algebraic numbers: the Hartmanis-Stearns problem revisited
Succinctness as a source of complexity in logical formalisms
A formalization of multi-tape Turing machines
Efficient algorithms for membership in Boolean hierarchies of regular languages
Some remarks on real numbers induced by first-order spectra
Weak completeness in $\text{E}$ and $\text{E}_{2}$
Resource restricted computability theoretic learning: Illustrative topics and problems
Towards separating nondeterminism from determinism
Hierarchies of Turing machines with restricted tape alphabet size
Indistinguishability and First-Order Logic
On small, reduced, and fast universal accepting networks of splicing processors
Semi-Galois categories. II: An arithmetic analogue of Christol's theorem
Complexity theory basics: NP and NL
Indirect addressing and the time relationships of some models of sequential computation
The theory of languages
On the power of several queues
Programs=data=first-class citizens in a computational world
Complexity of algorithms and computations
A note on the best-case complexity
On the size complexity of hybrid networks of evolutionary processors
Translational lemmas, polynomial time, and $(\log n)^j$-space
Effective guessing has unlikely consequences
Differentially oblivious Turing machines
Block rigidity: strong multiplayer parallel repetition implies super-linear lower bounds for Turing machines
Theory of -languages. I: Characterizations of -context- free languages
Deciding according to the shortest computations

This page was built for publication: On the Computational Complexity of Algorithms

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