Definitions

• S ={a,b,c} - symbol alphabet, ? ={x,y,v} - parameter alphabet

• p-strings: (S + ? )*

• P1: p1 & p2 are p-matches iff p1 can be transformed into p2 by a one-to-one mapping

  S=axayb
  
  T=avaxb

• prev(S) -

  • leftmost occurrence of each parameter becomes 0
  • subsequent occurrences replaced by difference in position compared to previous occurrence: parameter pointer
    prev(abuvabuvu) = ab00ab442
  • S & S’ are p-matches iff prev(S)=prev(S’)

Previous slide

Next slide

Back to first slide

View graphic version