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: Torben �gidius Mogensen on 23 Jun 2010 04:02
Daniel Pitts <newsgroup.spamfilter(a)virtualinfinity.net> writes:

> On 6/22/2010 9:24 AM, Piotr Wyderski wrote:

> 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.

You can emulate a 2DFA in linear time by using a simplified variant of
Cook's construction for linear-time emulation of 2PDAs.

Torben
First  |  Prev  | 
Pages: 1 2
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