Class: Lernen::Algorithm::Procedural::ProceduralLearner

Inherits:
Learner
  • Object
show all
Defined in:
lib/lernen/algorithm/procedural/procedural_learner.rb

Overview

ProceduralLearner is an implementation of the learning algorithm for SPA.

This algorithm is described in [Frohme & Seffen (2021) “Compositional Learning of Mutually Recursive Procedural Systems”](link.springer.com/article/10.1007/s10009-021-00634-y).

Instance Method Summary collapse

Methods inherited from Learner

#add_alphabet, #learn

Constructor Details

#initialize(alphabet, call_alphabet, return_input, sul, algorithm: :kearns_vazirani, algorithm_params: {}, cex_processing: :binary, scan_procs: true) ⇒ ProceduralLearner

: (

  Array[In] alphabet,
  Array[Call] call_alphabet,
  Return return_input,
  System::SUL[In | Call | Return, bool] sul,
  ?algorithm: :lstar | :kearns_vazirani | :lsharp,
  ?algorithm_params: Hash[Symbol, untyped],
  ?cex_processing: cex_processing_method,
  ?scan_procs: bool
) -> void


39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# File 'lib/lernen/algorithm/procedural/procedural_learner.rb', line 39

def initialize(
  alphabet,
  call_alphabet,
  return_input,
  sul,
  algorithm: :kearns_vazirani,
  algorithm_params: {},
  cex_processing: :binary,
  scan_procs: true
)
  super()

  @alphabet = alphabet.dup
  @call_alphabet = call_alphabet.dup
  @return_input = return_input
  @sul = sul
  @algorithm = algorithm
  @algorithm_params = algorithm_params
  @cex_processing = cex_processing

  @initial_proc = nil
  @proc_to_learner = {}
  @manager = ATRManager.new(alphabet, call_alphabet, return_input, scan_procs:)
  @active_call_alphabet_set = Set.new
end

Instance Method Details

#build_hypothesisObject

: () -> [Automaton::SPA[In, Call, Return], Hash[Call, Hash[Integer, Array[In | Call]]]]



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# File 'lib/lernen/algorithm/procedural/procedural_learner.rb', line 66

def build_hypothesis
  initial_proc = @initial_proc
  return build_first_hypothesis, {} unless initial_proc

  proc_to_dfa = {}
  proc_to_state_to_prefix = {}
  @proc_to_learner.each do |proc, learner|
    dfa, state_to_prefix = learner.build_hypothesis
    proc_to_dfa[proc] = dfa
    proc_to_state_to_prefix[proc] = state_to_prefix
  end

  hypothesis = Automaton::SPA.new(initial_proc, @return_input, proc_to_dfa)
  [hypothesis, proc_to_state_to_prefix]
end

#refine_hypothesis(cex, _hypothesis, _proc_to_state_to_prefix) ⇒ Object

: (

  Array[In | Call | Return] cex,
  Automaton::SPA[In, Call, Return] _hypothesis,
  Hash[Call, Hash[Integer, Array[In | Call]]] _proc_to_state_to_prefix
) -> void


87
88
89
90
91
# File 'lib/lernen/algorithm/procedural/procedural_learner.rb', line 87

def refine_hypothesis(cex, _hypothesis, _proc_to_state_to_prefix)
  extract_useful_information_from_cex(cex)

  loop { break unless refine_hypothesis_internal(cex) }
end