wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

automata_two_way (725B)

      1 # Automata two way
      2 
      3 [Automata] that can read the input [word] in both directions
      4 
      5 It is an [open_problem] if two-way automata can be [automata_determinized] in [PTIME]. This is related to open problems in [complexity_theory], cf [kapoutsis2013two]: [sakoda_sipser_conjecture]
      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