|DFA transition table reduction by alphabet reduction. firstname.lastname@example.org (Christian Riis) (2003-02-21)|
|Re: DFA transition table reduction by alphabet reduction. email@example.com (Clint Olsen) (2003-02-24)|
|Re: DFA transition table reduction by alphabet reduction. firstname.lastname@example.org (Christian Riis) (2003-03-09)|
|Re: DFA transition table reduction by alphabet reduction. email@example.com (Glen Herrmannsfeldt) (2003-03-14)|
|From:||Christian Riis <firstname.lastname@example.org>|
|Date:||21 Feb 2003 00:50:07 -0500|
|Organization:||Department of Computer Science, University of Copenhagen|
|Keywords:||lex, optimize, question|
|Posted-Date:||21 Feb 2003 00:50:07 EST|
I'm writing a project about a certain scheme to reduce the size of DFA
transition tables. The idea is to make transtions on only a certain
number of the bits (half the bits for instance) in the letters in the
alfabet of a given DFA to an intermediate state and from there make
transitions on the rest of the bits. If one splits the transitions up
in two halves of equal size, the number of letters in the resulting
alfabet will of course have as many letters as the square root of the
number of letters in the original alfabet. What I'm hoping is, that
the number of states will increase less than the decrease of letters.
Does anyone in this forum know of any articles, books, whatever
written about this and if so, where can I find them?
Return to the
Search the comp.compilers archives again.