DFA transition table reduction by alphabet reduction.

Christian Riis <criis@tyr.diku.dk>
21 Feb 2003 00:50:07 -0500

          From comp.compilers
Related articles
DFA transition table reduction by alphabet reduction. criis@tyr.diku.dk (Christian Riis) (2003-02-21)
Re: DFA transition table reduction by alphabet reduction. clint@0lsen.net (Clint Olsen) (2003-02-24)
Re: DFA transition table reduction by alphabet reduction. criis@ivalde.diku.dk (Christian Riis) (2003-03-09)
Re: DFA transition table reduction by alphabet reduction. gah@ugcs.caltech.edu (Glen Herrmannsfeldt) (2003-03-14)
| List of all articles for this month |
From: Christian Riis <criis@tyr.diku.dk>
Newsgroups: comp.compilers
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

Hi.


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?


Regards.
Christian Riis

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.