scientific article

zbMath0574.68040MaRDI QIDQ3692869

Māris Alberts

Publication date: 1985

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

zbMATH Keywords

recognition of non-regular languages

Mathematics Subject Classification ID

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

Related Items (15)

Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ Weak and strong one-way space complexity classes ⋮ A remark on middle space bounded alternating Turing machines ⋮ Remarks on languages acceptable in log log n space ⋮ Pushdown and one-counter automata: constant and non-constant memory usage ⋮ Passively mobile communicating machines that use restricted space ⋮ A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines ⋮ Two-Way Automata versus Logarithmic Space ⋮ A survey of space complexity ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ Two-way automata versus logarithmic space ⋮ Pushdown automata and constant height: decidability and bounds ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Some notes on strong and weak log log n space complexity ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space

This page was built for publication: