STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES

DOI10.1142/S0129054114400292zbMath1318.68109OpenAlexW2139716557MaRDI QIDQ5247180

Martin Kutrib, Matthias Wendlandt, Andreas Malcher

Publication date: 23 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054114400292

zbMATH Keywords

undecidabilitydecidabilitydeterministic finite automatonpebble automatonhead hierarchyinclusion hierarchymulti-head automatonpebble hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Cellular Automata: Descriptional Complexity and Decidability

Cites Work

• On stateless deterministic restarting automata
• Complexity of multi-head finite automata: origins and directions
• On stateless multihead automata: hierarchies and the emptiness problem
• Hierarchies of one-way multihead automata languages
• ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA
• ON STATELESS AUTOMATA AND P SYSTEMS
• Three write heads are as good ask
• One-way multihead writing finite automata
• k + 1 Heads Are Better than k
• On Multi-Head Finite Automata
• Language recognition by marking automata
• One-way multihead finite automata and 2-bounded languages

This page was built for publication: STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES