automata_two_way (599B)
1 # Automata two way 2 3 [Automata] that can read the input [word] in both directions 4 5 [Automata_two_way_determinization] 6 7 Can be converted back to [automata_one_way]. 8 - Elementary construction to get an [automata_nondeterministic] for the complement language in [vardi1989note] with exp(n) blowup 9 - Elementary construction to get an [automata_deterministic] for the language in [shepherdson1959reduction] with exp(n^2) blowup 10 11 Generalization: [Two_way_nondeterministic_pushdown_automaton] 12 13 Up: [automata] 14 15 See also: [2rpq] 16 17 Aliases: two-way automaton, two-way automata, 2 way automaton, 2 way automata