Re: FSM union,intersection,factoring

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 05/14/04

  • Next message: Fredrik Manne: "Re: PhD position available" 
    Date: Thu, 13 May 2004 23:52:26 -0600

    On 13 May 2004, V.Z.Nuri wrote:

    > about a decade ago I discovered a n^2 algorithm to
    > compute A/\B and A\/B (intersection, union) for epsilon free FSMs.
    > its quite simple, just doing
    > a simultaneous traversal of both graphs, so I presume
    > its in the literature somewhere. however, I have not
    > heard of it anywhere. does anyone know? (my own favorite
    > ref, hopcroft/ullman, define A/\B and A\/B in terms
    > of epsilon transitions, which can be removed with another
    > algorithm. but maybe the combination of their two algorithms
    > is the same as the n^2 dual-traversal algorithm.)

      The computation through a machine C which is the cross product
    construction of A and B essentially performs a traversal through both
    machines. The cross product construction (of DFAs) is the standard method
    to show that regular languages are closed under union and intersection.
    The size of the cross product machine C is O(|A|*|B|), so this is probably
    the same thing as the n^2 algorithm you are referring to.

    > given C and C=A/\B or C=A\/B, find suitable A,B. ie
    > "factor" the FSM C into a union or intersection of two
    > other FSMs A,B. I have not been able to find a discussion or
    > reference to this problem in the literature. esp seeking software
    > although it seems unlikely. I have the
    > nagging suspicion that group theory would be quite relevant,
    > but dont know the specifics. I know that there is an infinite
    > set of FSMs A,B but presumably there is in some sense
    > "canonical" factors.

      The problem is not studied probably because not only is it the case that
    C can be decomposed into an infinite number of pairs (A,B), but also
    because if C is regular and C=A int B or C = A union B, then it is not
    even the case that A and B must be regular languages (they could even be
    undecidable languages.)
      One sense of 'canonical' factors - in the sense that there will be a
    unique factorization - is to factor C into (A,B) = (U,C) if C=A int B, and
    where U = the universal set, or (A,B) = (N,C) if C=A union B and where N =
    the empty set.

      Of course, you can always feel free to define your own notion of a
    canonical factorization and see where it leads.

    J

  • Next message: Fredrik Manne: "Re: PhD position available"
    • Quantcast