Module: Lernen

Defined in:
lib/lernen.rb,
lib/lernen/equiv.rb,
lib/lernen/graph.rb,
lib/lernen/system.rb,
lib/lernen/version.rb,
lib/lernen/algorithm.rb,
lib/lernen/automaton.rb,
lib/lernen/system/sul.rb,
lib/lernen/equiv/oracle.rb,
lib/lernen/automaton/dfa.rb,
lib/lernen/automaton/spa.rb,
lib/lernen/automaton/vpa.rb,
lib/lernen/algorithm/lstar.rb,
lib/lernen/automaton/mealy.rb,
lib/lernen/automaton/moore.rb,
lib/lernen/algorithm/lsharp.rb,
lib/lernen/system/block_sul.rb,
lib/lernen/algorithm/learner.rb,
lib/lernen/automaton/proc_util.rb,
lib/lernen/algorithm/procedural.rb,
lib/lernen/automaton/moore_like.rb,
lib/lernen/equiv/combined_oracle.rb,
lib/lernen/system/moore_like_sul.rb,
lib/lernen/algorithm/cex_processor.rb,
lib/lernen/equiv/test_words_oracle.rb,
lib/lernen/equiv/random_walk_oracle.rb,
lib/lernen/equiv/random_word_oracle.rb,
lib/lernen/algorithm/kearns_vazirani.rb,
lib/lernen/equiv/spa_simulator_oracle.rb,
lib/lernen/equiv/vpa_simulator_oracle.rb,
lib/lernen/automaton/transition_system.rb,
lib/lernen/system/moore_like_simulator.rb,
lib/lernen/algorithm/cex_processor/acex.rb,
lib/lernen/algorithm/kearns_vazirani_vpa.rb,
lib/lernen/algorithm/lstar/lstar_learner.rb,
lib/lernen/equiv/exhaustive_search_oracle.rb,
lib/lernen/algorithm/lsharp/lsharp_learner.rb,
lib/lernen/algorithm/procedural/atr_manager.rb,
lib/lernen/algorithm/lsharp/observation_tree.rb,
lib/lernen/algorithm/lstar/observation_table.rb,
lib/lernen/equiv/moore_like_simulator_oracle.rb,
lib/lernen/system/transition_system_simulator.rb,
lib/lernen/algorithm/procedural/procedural_sul.rb,
lib/lernen/equiv/random_well_matched_word_oracle.rb,
lib/lernen/algorithm/procedural/procedural_learner.rb,
lib/lernen/algorithm/procedural/return_indices_acex.rb,
lib/lernen/equiv/transition_system_simulator_oracle.rb,
lib/lernen/algorithm/kearns_vazirani/discrimination_tree.rb,
lib/lernen/algorithm/cex_processor/prefix_transformer_acex.rb,
lib/lernen/algorithm/kearns_vazirani/kearns_vazirani_learner.rb,
lib/lernen/algorithm/kearns_vazirani_vpa/discrimination_tree_vpa.rb,
lib/lernen/algorithm/kearns_vazirani_vpa/kearns_vazirani_vpa_learner.rb

Overview

rbs_inline: enabled

Defined Under Namespace

Modules: Algorithm, Automaton, Equiv, System Classes: Graph

Constant Summary collapse

VERSION =

The version string.

"0.3.0"

Class Method Summary collapse

Class Method Details

.learn(alphabet:, call_alphabet: nil, return_alphabet: nil, return_input: nil, sul: nil, oracle: nil, oracle_params: {}, algorithm: nil, automaton_type: nil, params: {}, random: Random, &sul_block) ⇒ Object

Learn an automaton by using the given parameters.

This method is a frontend of the learning algorithms. Actual implementations are placed under the ‘Lernen::Algorithm` namespace.

## Parameters

This method takes a lot of parameters, but almost of parameters are optional. To start learning, we need to give ‘alphabet` and a block of a program to infer an automaton.

  • ‘alphabet`: An input alphabet. This must be given as an `Array` object.

  • ‘call_alphabet`: A call input alphabet of VPA. If this is specified, `automaton_type` is specified as `:vpa` automatically.

  • ‘return_alphabet`: A return input alphabet of VPA.

  • ‘sul`: A system under learning. If an automaton instance is given, it is converted it to a simulator and use it as a SUL. Or, if it is not specified, we use a block as a SUL.

  • ‘oracle`: An equivalence oracle. It is one of `:exhaustive_search`, `:random_walk`, `:random_word`, or an actual instance of `Equiv::Oracle`. If the value is a symbol, an `Equiv::Oracle` instance of the specified kind is created with `oracle_params`. The default value is `:random_word` if `automaton_type` is one of `:dfa`, `:moore`, and `:mealy`, or the default value is `:random_well_matched_word` if `automaton_type` is either `:spa` or `:vpa`.

  • ‘oracle_params`: A hash of parameters for equivalence oracle. The default value is `{}`.

  • ‘algorithm`: An algorithm name to use. It is one of `:lstar`, `:kearns_vazirani`, or `:lsharp`. The default value is `:kearns_vazirani` (if `automaton_type` is one of `:dfa`, `:moore`, and `:mealy`), or `:kearns_vazirani_vpa` (if `automaton_type` is `vpa`), or `:procedural` (if `automaton_type` is `spa`).

  • ‘automaton_type`: A type of automaton to infer. It is one of `:dfa`, `:mealy`, `:moore`, `:vpa`, and `:spa`. The default value is `:dfa`, but it becomes `:vpa` or `:spa` if `call_alphabet` or `return_input` is specified.

  • ‘params`: A hash of parameter to pass a learning algorithm. The default value is `{}`.

  • ‘random`: A PRNG instance. It is used by an equivalence oracle.

: [In] (

  alphabet: Array[In],
  sul: Automaton::DFA[In] | System::MooreLikeSUL[In, bool],
  ?oracle: oracle_type | Equiv::Oracle[In, bool],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: algorithm_name,
  ?automaton_type: :dfa,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) -> Automaton::DFA[In]

: [In] (

  alphabet: Array[In],
  ?oracle: oracle_type | Equiv::Oracle[In, bool],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: algorithm_name,
  ?automaton_type: :dfa,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) { (Array[In]) -> bool } -> Automaton::DFA[In]

: [In, Out] (

  alphabet: Array[In],
  sul: Automaton::Mealy[In, Out] | System::SUL[In, Out],
  ?oracle: oracle_type | Equiv::Oracle[In, Out],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: algorithm_name,
  automaton_type: :mealy,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) -> Automaton::Mealy[In, Out]

: [In, Out] (

  alphabet: Array[In],
  ?oracle: oracle_type | Equiv::Oracle[In, Out],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: algorithm_name,
  automaton_type: :mealy,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) { (Array[In]) -> Out } -> Automaton::Mealy[In, Out]

: [In, Out] (

  alphabet: Array[In],
  sul: Automaton::Moore[In, Out] | System::MooreLikeSUL[In, Out],
  ?oracle: oracle_type | Equiv::Oracle[In, Out],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: algorithm_name,
  automaton_type: :moore,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) -> Automaton::Moore[In, Out]

: [In, Out] (

  alphabet: Array[In],
  ?oracle: oracle_type | Equiv::Oracle[In, Out],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: algorithm_name,
  automaton_type: :moore,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) { (Array[In]) -> Out } -> Automaton::Moore[In, Out]

: [In, Call, Return] (

  alphabet: Array[In],
  call_alphabet: Array[Call],
  return_alphabet: Array[Return],
  sul: Automaton::VPA[In, Call, Return] | System::MooreLikeSUL[In | Call | Return, bool],
  ?oracle: oracle_type | Equiv::Oracle[In | Call | Return, bool],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: :kearns_vazirani_vpa,
  ?automaton_type: :vpa,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) -> Automaton::VPA[In, Call, Return]

: [In, Call, Return] (

  alphabet: Array[In],
  call_alphabet: Array[Call],
  return_alphabet: Array[Return],
  ?oracle: oracle_type | Equiv::Oracle[In | Call | Return, bool],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: :kearns_vazirani_vpa,
  ?automaton_type: :vpa,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) { (Array[In | Call | Return]) -> bool } -> Automaton::VPA[In, Call, Return]

: [In, Call, Return] (

  alphabet: Array[In],
  call_alphabet: Array[Call],
  return_input: Return,
  sul: Automaton::SPA[In, Call, Return] | System::MooreLikeSUL[In | Call | Return, bool],
  ?oracle: oracle_type | Equiv::Oracle[In | Call | Return, bool],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: :procedural,
  ?automaton_type: :spa,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) -> Automaton::SPA[In, Call, Return]

: [In, Call, Return] (

  alphabet: Array[In],
  call_alphabet: Array[Call],
  return_input: Return,
  ?oracle: oracle_type | Equiv::Oracle[In | Call | Return, bool],
  ?oracle_params: Hash[Symbol, untyped],
  ?algorithm: :procedural,
  ?automaton_type: :spa,
  ?params: Hash[Symbol, untyped],
  ?random: Random
) { (Array[In | Call | Return]) -> bool } -> Automaton::SPA[In, Call, Return]



221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
 
# File 'lib/lernen.rb', line 221

def self.learn(
  alphabet:,
  call_alphabet: nil,
  return_alphabet: nil,
  return_input: nil,
  sul: nil,
  oracle: nil,
  oracle_params: {},
  algorithm: nil,
  automaton_type: nil,
  params: {},
  random: Random,
  &sul_block
)
  automaton = nil

  case sul
  when System::SUL
    # Do nothing
  when Automaton::TransitionSystem
    automaton = sul
    oracle ||= :simulator
    automaton_type ||= sul.type
    sul = System.from_automaton(sul) # steep:ignore
  when nil
    sul = System.from_block(&sul_block) # steep:ignore
  else
    raise ArgumentError, "Unsupported SUL: #{sul}"
  end

  automaton_type ||=
    if call_alphabet
      return_input ? :spa : :vpa
    else
      :dfa
    end

  merged_alphabet =
    case automaton_type
    in :dfa | :moore | :mealy
      alphabet
    in :vpa | :spa
      return_alphabet ||= [return_input]
      alphabet + call_alphabet + return_alphabet
    end

  oracle ||= %i[vpa spa].include?(automaton_type) ? :random_well_matched_word : :random_word

  case oracle
  when Equiv::Oracle
    # Do nothing
  when :exhaustive_search
    oracle = Equiv::ExhaustiveSearchOracle.new(merged_alphabet, sul, **oracle_params)
  when :random_walk
    oracle = Equiv::RandomWalkOracle.new(merged_alphabet, sul, random:, **oracle_params)
  when :random_word
    oracle = Equiv::RandomWordOracle.new(merged_alphabet, sul, random:, **oracle_params)
  when :random_well_matched_word
    oracle =
      Equiv::RandomWellMatchedWordOracle.new(
        alphabet,
        call_alphabet, # steep:ignore
        return_alphabet, # steep:ignore
        sul,
        random:,
        **oracle_params
      )
  when :simulator
    oracle =
      case automaton
      when Automaton::Mealy
        Equiv::TransitionSystemSimulatorOracle.new(alphabet, automaton, sul)
      when Automaton::DFA, Automaton::Moore
        Equiv::MooreLikeSimulatorOracle.new(alphabet, automaton, sul)
      when Automaton::VPA
        Equiv::VPASimulatorOracle.new(alphabet, call_alphabet, return_alphabet, automaton, sul) # steep:ignore
      when Automaton::SPA
        Equiv::SPASimulatorOracle.new(alphabet, call_alphabet, automaton, sul) # steep:ignore
      else
        raise ArgumentError, "Cannot simulate automaton: #{automaton}"
      end
  else
    raise ArgumentError, "Unsupported oracle: #{oracle}"
  end

  algorithm ||=
    case automaton_type
    in :dfa | :moore | :mealy
      :kearns_vazirani
    in :vpa
      :kearns_vazirani_vpa
    in :spa
      :procedural
    end

  case algorithm
  in :lstar
    Algorithm::LStar.learn(alphabet, sul, oracle, automaton_type:, **params)
  in :kearns_vazirani
    Algorithm::KearnsVazirani.learn(alphabet, sul, oracle, automaton_type:, **params)
  in :kearns_vazirani_vpa
    Algorithm::KearnsVaziraniVPA.learn(alphabet, call_alphabet, return_alphabet, sul, oracle, **params)
  in :lsharp
    Algorithm::LSharp.learn(alphabet, sul, oracle, automaton_type:, **params)
  in :procedural
    Algorithm::Procedural.learn(alphabet, call_alphabet, return_input, sul, oracle, **params)
  end
end