scientific article

zbMath0415.68012MaRDI QIDQ3051378

Wolfgang J. Paul

Publication date: 1979

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

zbMATH Keywords

sorting algorithmsKolmogorov complexity of stringsnonlinear lower bound for the runtime

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (9)

String-matching cannot be done by a two-head one-way deterministic finite automaton ⋮ On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ New lower bounds for element distinctness on a one-tape Turing machine ⋮ k\(+1\) heads are better than k for PDAs ⋮ An information-theoretic approach to time bounds for on-line computation ⋮ Kolmogorov complexity and random graphs ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness ⋮ The complexity of matrix transposition on one-tape off-line Turing machines ⋮ Three one-way heads cannot do string matching

This page was built for publication: