On pebble automata

DOI10.1016/0304-3975(86)90112-XzbMath0612.68045MaRDI QIDQ1088408

Michael A. Palis, Jik H. Chang, Oscar H. Ibarra, Bala Ravikumar

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

accepted languagesrecognition powerspace-bounded Turing machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions ⋮ A note on alternating one-pebble Turing machines with sublogarithmic space ⋮ The equivalence of pebbles and sensing heads for finite automata ⋮ Automata with Modulo Counters and Nondeterministic Counter Bounds ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties ⋮ The complexity of ranking simple languages ⋮ Factoring and Testing Primes in Small Space ⋮ Some properties of one-pebble Turing machines with sublogarithmic space ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Halting space-bounded computations
• On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
• Space bounds for processing contentless inputs
• On tape bounds for single letter alphabet language processing
• Checking automata and one-way stack languages
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• An Infinite Hierarchy of Context-Free Languages
• One-tape, off-line Turing machine computations
• Language recognition by marking automata
• Time and tape complexity of pushdown automaton languages