Method: Stamina::Induction::RPNI#main

Defined in:
lib/stamina-induction/stamina/induction/rpni.rb

#main(ufds) ⇒ Object

Main method of the algorithm. Refines the union find passed as first argument by merging well chosen state pairs. Returns the refined union find.

Preconditions:

  • The union find ufds is correctly initialized (contains :initial, :accepting, and :error boolean flags as well as a :delta sub hash)

Postconditions:

  • The union find has been refined. It encodes a quotient automaton (of the PTA it comes from) such that all positive and negative strings of the underlying sample are correctly classified by it.



117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/stamina-induction/stamina/induction/rpni.rb', line 117

def main(ufds)
  @ufds = ufds
  info("Starting RPNI (#{@ufds.size} states)")
  # First loop, iterating all PTA states
  (1...@ufds.size).each do |i|
    # we ignore those that have been previously merged
    next if @ufds.slave?(i)
    # second loop: states of lower rank, with ignore
    (0...i).each do |j|
      next if @ufds.slave?(j)
      # try to merge this pair, including determinization
      # simply break the loop if it works!
      success = successfull_merge_or_nothing(i,j)
      if success
        info("#{i} and #{j} successfully merged")
        break
      end
    end # j loop
  end # i loop
  @ufds
end