Name
Abstract | ||
|---|---|---|
Stateless variants of deterministic one-way multi-head finite automata with pebbles, that is, automata where the heads can drop, sense, and pick up pebbles, are studied. The relation between heads and pebbles is investigated, and a proper double hierarcliy concerning these two resources is obtained. Moreover, it is shown that a conversion of an arbitrary automaton to a stateless automaton can always be achieved at the cost of additional heads and/or pebbles. On the other hand, there are languages where one head cannot be traded for any number of additional pebbles and vice versa. Finally, the emptiness problem and related problems are shown to be undecidable even for the 'simplest' model, namely, for stateless one-way finite automata with two heads and one pebble. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1142/S0129054114400292 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Stateless multi-head finite automata, pebbles automata, head hierarchy, pebble hierarchy, decidability questions | Discrete mathematics,Combinatorics,Automaton,Finite-state machine,Pebble,Hierarchy,Stateless protocol,Versa,Mathematics,Undecidable problem | Journal |
Volume | Issue | ISSN |
25 | 8 | 0129-0541 |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Kutrib | 1 | 778 | 89.77 |
| Andreas Malcher | 2 | 204 | 39.40 |
| Matthias Wendlandt | 3 | 32 | 14.13 |