scientific article

zbMath0462.68028MaRDI QIDQ3912023

Rūsiņš Freivalds

Publication date: 1979

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

zbMATH Keywords

lower boundpalindromecrossing sequenceKolmogorov complexity of strings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (15)

Weak and strong one-way space complexity classes ⋮ A note on alternating one-pebble Turing machines with sublogarithmic space ⋮ Some observations concerning alternating Turing machines using small space ⋮ Remarks on languages acceptable in log log n space ⋮ There are no fully space constructible functions between log log n and log n ⋮ If deterministic and nondeterministic space complexities are equal for log log n then they are also equal for log n ⋮ If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n ⋮ A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines ⋮ Space bounded computations: Review and new separation results ⋮ A survey of space complexity ⋮ A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space ⋮ Some notes on strong and weak log log n space complexity ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space ⋮ Complexity lower bounds for machine computing models ⋮ The alternation hierarchy for sublogarithmic space is infinite

This page was built for publication: