activity
20202025
most citedThe maximum length of shortest accepted strings for direction-determinate two-way finite automata

1 citations · 1 across the 7 of their papers we have counts for

collaborators
Showing 2020Show all

1 paper · 1 filter

cs.FL2020

State complexity of halting, returning and reversible graph-walking automata

Olga Martynova, Alexander Okhotin

Graph-walking automata (GWA) traverse graphs by moving between the nodes following the edges, using a finite-state control to decide where to go next. It is known that every GWA ca…