I am currently studying two-way DFA and I couldn't find and research anything on its real-life applications if there are any. I am very unsure where it could be used and any ideas would be great. tyia

  • 1
    $\begingroup$ What kind of answer are you looking for? As a computational model, they are exponentially more succinct than their 1-way counterparts, so they allow easy modelling. Also, techniques that were developed for them, e.g., crossing-sequences, have proven useful in other models, e.g. string-to-string transducers. Is this what you consider "real life"? $\endgroup$
    – Shaull
    Aug 2, 2023 at 6:28
  • $\begingroup$ Not directly related, but you can check multi-pass streaming algorithms. $\endgroup$ Aug 3, 2023 at 8:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.