Implement Symbolic Transducer

Glavin001 commented 8 years ago

t = STF()    # t is a standard form transducer

t.productInput(a)
# does product construction between t and a
# but, when two transitions match it keeps both
# the input and output labels in the result

t.inIntersection(nfa)
# uses the above, but takes care of any empty
# input transitions and fixes final states

t.toOutNFA()
# returns NFA same as t but without the input labels

t.runOnNFA(a)

Glavin001 commented 8 years ago

Unittest: https://docs.python.org/2/library/unittest.html#unittest-skipping
Profiling Python Like a Boss: https://zapier.com/engineering/profiling-python-boss/
TimeComplexity: https://wiki.python.org/moin/TimeComplexity

Glavin001 commented 8 years ago

Some performance tests:

Using SFT
         282 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 copy.py:113(_copy_with_constructor)
        1    0.000    0.000    0.000    0.000 copy.py:66(copy)
        3    0.000    0.000    0.000    0.000 fa.py:117(__init__)
        3    0.000    0.000    0.000    0.000 fa.py:1560(__init__)
        1    0.000    0.000    0.000    0.000 fa.py:1828(setInitial)
        1    0.000    0.000    0.000    0.000 fa.py:1834(addInitial)
        1    0.000    0.000    0.000    0.000 fa.py:2001(epsilonP)
        1    0.000    0.000    0.000    0.000 fa.py:2005(<lambda>)
        4    0.000    0.000    0.000    0.000 fa.py:259(addState)
        2    0.000    0.000    0.000    0.000 fa.py:350(setFinal)
        1    0.000    0.000    0.000    0.000 fa.py:359(addFinal)
        3    0.000    0.000    0.000    0.000 fa.py:376(setSigma)
       29    0.000    0.000    0.000    0.000 fa.py:395(stateIndex)
        1    0.000    0.000    0.000    0.000 fa.py:504(renameStates)
        8    0.000    0.000    0.000    0.000 fa.py:574(inputS)
        2    0.000    0.000    0.000    0.000 transducers.py:123(__init__)
       16    0.000    0.000    0.000    0.000 transducers.py:406(addTransitionQ)
        1    0.000    0.000    0.000    0.000 transducers.py:427(setInitial)
       32    0.000    0.000    0.000    0.000 transducers.py:443(addTransition)
        1    0.000    0.000    0.000    0.000 transducers.py:561(toInNFA)
        1    0.000    0.000    0.000    0.000 transducers.py:576(toOutNFA)
        1    0.000    0.000    0.000    0.000 transducers.py:595(inIntersection)
        1    0.000    0.000    0.000    0.000 transducers.py:623(productInput)
        1    0.000    0.000    0.000    0.000 transducers.py:766(runOnNFA)
        1    0.000    0.000    0.000    0.000 transducers.py:826(inverse)
        1    0.000    0.000    0.000    0.000 transducers.py:862(epsilonP)
        2    0.000    0.000    0.000    0.000 transducers.py:87(__init__)
        1    0.000    0.000    0.000    0.000 {any}
        2    0.000    0.000    0.000    0.000 {isinstance}
        5    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {map}
      101    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
        4    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        9    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
       26    0.000    0.000    0.000    0.000 {method 'index' of 'list' objects}
        4    0.000    0.000    0.000    0.000 {method 'intersection' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'itervalues' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'keys' of 'dict' objects}
        4    0.000    0.000    0.000    0.000 {method 'pop' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'union' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {range}

Using SSFT
         268 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 copy.py:113(_copy_with_constructor)
        1    0.000    0.000    0.000    0.000 copy.py:66(copy)
        3    0.000    0.000    0.000    0.000 fa.py:117(__init__)
        3    0.000    0.000    0.000    0.000 fa.py:1560(__init__)
        1    0.000    0.000    0.000    0.000 fa.py:1828(setInitial)
        1    0.000    0.000    0.000    0.000 fa.py:1834(addInitial)
        1    0.000    0.000    0.000    0.000 fa.py:2001(epsilonP)
        1    0.000    0.000    0.000    0.000 fa.py:2005(<lambda>)
        4    0.000    0.000    0.000    0.000 fa.py:259(addState)
        2    0.000    0.000    0.000    0.000 fa.py:350(setFinal)
        1    0.000    0.000    0.000    0.000 fa.py:359(addFinal)
        3    0.000    0.000    0.000    0.000 fa.py:376(setSigma)
       28    0.000    0.000    0.000    0.000 fa.py:395(stateIndex)
        1    0.000    0.000    0.000    0.000 fa.py:504(renameStates)
        8    0.000    0.000    0.000    0.000 fa.py:574(inputS)
        1    0.000    0.000    0.000    0.000 transducers.py:1119(productInput)
        2    0.000    0.000    0.000    0.000 transducers.py:123(__init__)
       15    0.000    0.000    0.000    0.000 transducers.py:406(addTransitionQ)
        1    0.000    0.000    0.000    0.000 transducers.py:427(setInitial)
       30    0.000    0.000    0.000    0.000 transducers.py:443(addTransition)
        1    0.000    0.000    0.000    0.000 transducers.py:561(toInNFA)
        1    0.000    0.000    0.000    0.000 transducers.py:576(toOutNFA)
        1    0.000    0.000    0.000    0.000 transducers.py:595(inIntersection)
        1    0.000    0.000    0.000    0.000 transducers.py:766(runOnNFA)
        1    0.000    0.000    0.000    0.000 transducers.py:826(inverse)
        1    0.000    0.000    0.000    0.000 transducers.py:862(epsilonP)
        2    0.000    0.000    0.000    0.000 transducers.py:87(__init__)
        1    0.000    0.000    0.000    0.000 {any}
        2    0.000    0.000    0.000    0.000 {isinstance}
        5    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {map}
       94    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
        4    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {method 'discard' of 'set' objects}
        9    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
       25    0.000    0.000    0.000    0.000 {method 'index' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'itervalues' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'keys' of 'dict' objects}
        4    0.000    0.000    0.000    0.000 {method 'pop' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'union' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {range}

Glavin001 commented 8 years ago

More performance tests (1000 iterations):

Using SFT:
         281718 function calls in 0.189 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      999    0.001    0.000    0.001    0.000 copy.py:113(_copy_with_constructor)
      999    0.001    0.000    0.002    0.000 copy.py:66(copy)
     2997    0.003    0.000    0.003    0.000 fa.py:117(__init__)
     2997    0.003    0.000    0.006    0.000 fa.py:1560(__init__)
      999    0.001    0.000    0.001    0.000 fa.py:1828(setInitial)
      999    0.000    0.000    0.001    0.000 fa.py:1834(addInitial)
      999    0.002    0.000    0.005    0.000 fa.py:2001(epsilonP)
      999    0.000    0.000    0.000    0.000 fa.py:2005(<lambda>)
     3996    0.003    0.000    0.005    0.000 fa.py:259(addState)
     1998    0.001    0.000    0.001    0.000 fa.py:350(setFinal)
      999    0.000    0.000    0.001    0.000 fa.py:359(addFinal)
     2997    0.001    0.000    0.001    0.000 fa.py:376(setSigma)
    28971    0.016    0.000    0.028    0.000 fa.py:395(stateIndex)
      999    0.001    0.000    0.002    0.000 fa.py:504(renameStates)
     7992    0.005    0.000    0.007    0.000 fa.py:574(inputS)
     1998    0.002    0.000    0.009    0.000 transducers.py:123(__init__)
    15984    0.016    0.000    0.059    0.000 transducers.py:406(addTransitionQ)
      999    0.001    0.000    0.001    0.000 transducers.py:427(setInitial)
    31968    0.037    0.000    0.045    0.000 transducers.py:443(addTransition)
      999    0.010    0.000    0.015    0.000 transducers.py:561(toInNFA)
      999    0.002    0.000    0.057    0.000 transducers.py:576(toOutNFA)
      999    0.005    0.000    0.130    0.000 transducers.py:595(inIntersection)
      999    0.031    0.000    0.115    0.000 transducers.py:623(productInput)
      999    0.002    0.000    0.189    0.000 transducers.py:766(runOnNFA)
      999    0.012    0.000    0.040    0.000 transducers.py:826(inverse)
      999    0.001    0.000    0.001    0.000 transducers.py:862(epsilonP)
     1998    0.003    0.000    0.007    0.000 transducers.py:87(__init__)
      999    0.000    0.000    0.000    0.000 {any}
     1998    0.001    0.000    0.001    0.000 {isinstance}
     4995    0.001    0.000    0.001    0.000 {len}
      999    0.003    0.000    0.003    0.000 {map}
   100899    0.011    0.000    0.011    0.000 {method 'add' of 'set' objects}
     3996    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
      999    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     8991    0.001    0.000    0.001    0.000 {method 'get' of 'dict' objects}
    25974    0.008    0.000    0.008    0.000 {method 'index' of 'list' objects}
     3996    0.001    0.000    0.001    0.000 {method 'intersection' of 'set' objects}
      999    0.000    0.000    0.000    0.000 {method 'itervalues' of 'dict' objects}
      999    0.000    0.000    0.000    0.000 {method 'keys' of 'dict' objects}
     3996    0.000    0.000    0.000    0.000 {method 'pop' of 'set' objects}
      999    0.001    0.000    0.001    0.000 {method 'union' of 'set' objects}
      999    0.001    0.000    0.001    0.000 {range}

Using SSFT:
         277722 function calls in 0.201 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      999    0.001    0.000    0.001    0.000 copy.py:113(_copy_with_constructor)
      999    0.001    0.000    0.002    0.000 copy.py:66(copy)
     2997    0.003    0.000    0.003    0.000 fa.py:117(__init__)
     2997    0.003    0.000    0.006    0.000 fa.py:1560(__init__)
      999    0.000    0.000    0.000    0.000 fa.py:1828(setInitial)
      999    0.000    0.000    0.001    0.000 fa.py:1834(addInitial)
      999    0.001    0.000    0.005    0.000 fa.py:2001(epsilonP)
      999    0.000    0.000    0.000    0.000 fa.py:2005(<lambda>)
     3996    0.004    0.000    0.005    0.000 fa.py:259(addState)
     1998    0.001    0.000    0.001    0.000 fa.py:350(setFinal)
      999    0.000    0.000    0.001    0.000 fa.py:359(addFinal)
     2997    0.001    0.000    0.001    0.000 fa.py:376(setSigma)
    28971    0.016    0.000    0.028    0.000 fa.py:395(stateIndex)
      999    0.001    0.000    0.002    0.000 fa.py:504(renameStates)
     7992    0.005    0.000    0.007    0.000 fa.py:574(inputS)
      999    0.038    0.000    0.125    0.000 transducers.py:1119(productInput)
     1998    0.002    0.000    0.009    0.000 transducers.py:123(__init__)
    15984    0.016    0.000    0.063    0.000 transducers.py:406(addTransitionQ)
      999    0.001    0.000    0.001    0.000 transducers.py:427(setInitial)
    31968    0.040    0.000    0.049    0.000 transducers.py:443(addTransition)
      999    0.010    0.000    0.016    0.000 transducers.py:561(toInNFA)
      999    0.002    0.000    0.057    0.000 transducers.py:576(toOutNFA)
      999    0.006    0.000    0.141    0.000 transducers.py:595(inIntersection)
      999    0.002    0.000    0.201    0.000 transducers.py:766(runOnNFA)
      999    0.012    0.000    0.040    0.000 transducers.py:826(inverse)
      999    0.001    0.000    0.001    0.000 transducers.py:862(epsilonP)
     1998    0.003    0.000    0.007    0.000 transducers.py:87(__init__)
      999    0.000    0.000    0.000    0.000 {any}
     1998    0.001    0.000    0.001    0.000 {isinstance}
     4995    0.001    0.000    0.001    0.000 {len}
      999    0.003    0.000    0.003    0.000 {map}
   100899    0.012    0.000    0.012    0.000 {method 'add' of 'set' objects}
     3996    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
      999    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     8991    0.001    0.000    0.001    0.000 {method 'get' of 'dict' objects}
    25974    0.009    0.000    0.009    0.000 {method 'index' of 'list' objects}
      999    0.000    0.000    0.000    0.000 {method 'itervalues' of 'dict' objects}
      999    0.000    0.000    0.000    0.000 {method 'keys' of 'dict' objects}
     3996    0.000    0.000    0.000    0.000 {method 'pop' of 'set' objects}
      999    0.000    0.000    0.000    0.000 {method 'union' of 'set' objects}
      999    0.001    0.000    0.001    0.000 {range}

SSFT: 0:00:00.204552, SFT: 0:00:00.192995

Glavin001 commented 8 years ago

A main objective for wanting symbolic machines is to decide efficiently whether

T.inIntersection(A).outIntersection(B).nonemptyW()

is None, where T is a SFT and A,B are automata. This has a certain meaning in coding theory. I see now that one also needs to define symbolic automata as well. Then,

[ ] define a utility function matchLabels(F, G) which returns the transducer label resulting by matching an automaton label F and a transducer label G.
[ ] define T.productInput(A) such that when it comes to matching the transition (p,F,q) of A and the transition (i,G,j) of T, the method adds the transition ((p,i), matchLabels(F,G), (q,i)) to the product transducer being constructed. Details follow.

How easy do you think is to allow set specs:

- @s                      #  the set of all alphabet symbols
- @{a1,a2,...,ak}    # the set of symbols a1,..,ak
- @!{a1,a2,...,ak}   # the set of symbols not = a1,..,ak
- a                         #  the set {a}
- @epsilon            # the set {@epsilon}
- @!a                     # all symbols not = a
and then have any of the above as automaton label,
and any of the following as Transducer labels:
- (x, y)      # the ordinary labels in SFT objects
- (X, d, Y)  # X,Y are set specs and d=0,1,2
where  (X,d,Y) means
- all pairs (x,y) with x in X, y in Y              (if d=0)
- all pairs (x,y) with x in X, y in Y, x != y,  (if d=1)
- all pairs (x,x) with x in both  X and Y      (if d=2)
Note that the ordinary label (x,y) is equiv to (x,0,y)
and also to (@{x}, 0, @{y})
Then the method matchLabels(F, (X,d,Y))  returns the
label (H, d, Y)  where  H is the intersection of  F and X

Glavin001 commented 8 years ago

New tasks:

1. Consider the NFA method   "A.__and__(B)"
   between NFAs A and B,  which returns an NFA
   accepting  L(A) intersection L(B)  ("__and__"
   relies on the NFA method "product"). Use it as a
   guide to define  the  product construction method
   A.toSFT(B), where  A and B are NFAs,  which
   would return an   SFT  T  as follows:
  ---
  Input alphabet    of T =  A.Sigma
  Output alphabet of T =  B.Sigma
  start states of T: all pairs (sA,sB), where
      sA=any start state of A, sB=any start state of B
  final states of T: all pairs (fA,fB), where
      fA=any final state of A, fB=any final state of B
 for any transitions (a1,x,a2) in A and (b1,y,b2) in B
      add the transition ((a1,b1), x/y, (a2,b2)) in T
 for any transition (a1,x,a2) in A and any state b in B
     add the transition ((a1,b), x/@epsilon,(a2,b)) in T
 for any state a in A and transition (b1,y,b2) in B
     add the transition ((a,b1),@epsilon/y, (a,b2)) in T

2. Define another product construction  method
   S.matchSFT(T), where S is SymbolicSFT and
   T is SFT,  returning an  SFT  W  as follows:
   Input alphabet = union of input alph. of S, T
   Output alphabet= union of those in S, T
   Start states: all pairs (sS,sT) where
      sS=any start state of S, sT=any start state of T
   final states of W: all pairs (fS,fT), where
      fS=any final state of S, fT=any final state of T
  for any transitions (s1,u/v,s2) in S and
          (t1,x/y,t2) in T, add the transition
      ((s1,t1), x/y, (s2,t2)) in W  iff   "u/v matches x/y"

3. We say that  "u/v  matches  x/y"  is true, if:
   u=x and v=y, or
   u/v = @s/@s and x=y and x,y != Epsilon,  or
   u/v = @s/@d and x!=y and x,y != Epsilon,  or
   u/v = @s/@epsilon and x != Epsilon and
                                   y= Epsilon,  or
   u/v = @epsilon/@s and x= Epsilon and y!=Epsilon

NOTE: With the above tools one would be able to
compute, for a given NFA  A  and SSFT  S, whether
S.match(A.toSFT(A) ).nonEmptyW()
returns (None,None), which is the equivalent of
S.inIntersection(A).outIntersection(A).nonEmptyW()

Glavin001 / FAdo

Implement Symbolic Transducer #1