wiki_research

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

word_automaton_two_way_one_way_conversion (420B)

      1 # Word automaton two way one way conversion
      2 
      3 - Elementary construction to get a [DFA] for the complement [formal_language] in [vardi1989note] with exp(n) blowup
      4 - Elementary construction to get a [DFA] for the language in [shepherdson1959reduction] with exp(n^2) blowup
      5 - Historical attribution in [morvan2025homomorphism] VII.1.1 p197
      6 
      7 Up: [conversion_automaton] of [word_automaton_two_way] to [word_automaton_one_way]