Re: working with very large Finite State Machines

"Rodney M. Bates" <rbates@southwind.net>
29 Apr 2001 02:08:02 -0400

          From comp.compilers

Related articles
working with very large Finite State Machines sjbradtke@home.com (Steve Bradtke) (2001-04-22)
Re: working with very large Finite State Machines vannoord@let.rug.nl (2001-04-26)
Re: working with very large Finite State Machines chase@world.std.com (David Chase) (2001-04-26)
Re: working with very large Finite State Machines rboland@unb.ca (Ralph Boland) (2001-04-26)
Re: working with very large Finite State Machines rbates@southwind.net (Rodney M. Bates) (2001-04-29)
| List of all articles for this month |

From: "Rodney M. Bates" <rbates@southwind.net>
Newsgroups: comp.compilers
Date: 29 Apr 2001 02:08:02 -0400
Organization: Compilers Central
References: 01-04-117
Keywords: lex
Posted-Date: 29 Apr 2001 02:08:02 EDT

I don't know if this applies to your problem, but in many FSMs with a
large state set, the state set can be cartesian factored into a tuple
of several components. Taken literally, the state set is the
cartesian product of the value sets of the components. The input set
might be factorable too.


Often, the transition function may then have patterns which allow it
to be expressed as a function of the components, much more
compactly. I don't know if such patterns and factorings exist in your
application. If not, then just defining the states and transitions is
a big problem too, because it has to be done by brute force
enumeration.


> I am working on a project that involves the construction of
> very large Finite State Machines (up to approximately 10^7 states).
> project.
--
Rodney M. Bates


Post a followup to this message

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