Two-way DFAs
in [Theory]
|
Prev: Musatov shows his writing chops: Prolog to new novel, sneek peek!
Next: POSTDOCTORAL POSITION in ALGORITHMS AND COMPLEXITY (ALGORITHMIC GAME THEORY), UNIV. of LIVERPOOL, UK
From: Piotr Wyderski on 21 Jun 2010 07:05 Hello, I would like to learn a bit about two-way Deterministic Finite Automata. I am particularly interested in their practical applications, namely the procedure of conversion from an NFA to a 2-DFA and its minimization. Could you please provide me some reference on the subject? Best regards Piotr Wyderski
From: Torben �gidius Mogensen on 22 Jun 2010 12:02 "Piotr Wyderski" <piotr.wyderski(a)mothers.against.spam.gmail.com> writes: > Hello, > > I would like to learn a bit about two-way Deterministic Finite > Automata. I am particularly interested in their practical applications, > namely the procedure of conversion from an NFA to a 2-DFA > and its minimization. Could you please provide me some reference > on the subject? Since any DFA is also a 2-DFA, you can use the normal NFA to DFA contruction. A 2-DFA can not recognize any language that is not also recognized by a DFA, but it may be more succint. I don't know about minimization, but I have a feeling it is not easy (or at least not both easy and efficient). Torben
From: Piotr Wyderski on 22 Jun 2010 12:24 Torben Agidius Mogensen wrote: > Since any DFA is also a 2-DFA, you can use the normal NFA to DFA > contruction. Well, of course it would be valid by definition, but the point is to skip the potentially exponential state space explosion during the process of conversion from NFA to DFA. If there is no algorithmic advantage in constructing 2-DFAs, then they are only of academic interest. But I believe there is huge potential to be explored... Best regards Piotr Wyderski
From: Daniel Pitts on 22 Jun 2010 19:45 On 6/22/2010 9:24 AM, Piotr Wyderski wrote: > Torben Agidius Mogensen wrote: > >> Since any DFA is also a 2-DFA, you can use the normal NFA to DFA >> contruction. > > Well, of course it would be valid by definition, but the point is to skip > the potentially exponential state space explosion during the process > of conversion from NFA to DFA. If there is no algorithmic advantage > in constructing 2-DFAs, then they are only of academic interest. But > I believe there is huge potential to be explored... Without having read anything on 2-DFAs, it sounds like a disguise for a NDA. If you might *try* going back, then you have reintroduced backtracking, which would cause potential run-time exponential growth for savings in the state graph. -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Torben �gidius Mogensen on 23 Jun 2010 04:00
"Piotr Wyderski" <piotr.wyderski(a)mothers.against.spam.gmail.com> writes: > Torben Agidius Mogensen wrote: > >> Since any DFA is also a 2-DFA, you can use the normal NFA to DFA >> contruction. > > Well, of course it would be valid by definition, but the point is to skip > the potentially exponential state space explosion during the process > of conversion from NFA to DFA. If there is no algorithmic advantage > in constructing 2-DFAs, then they are only of academic interest. But > I believe there is huge potential to be explored... You can escape exponential explosion in some cases, but there are still many NFAs that have exponentially larger 2DFAs. So you won't escape exponential explosion by using 2DFAs. Torben |