Skip to content

Repository files navigation

lstar-rocq

A collection of formally-verified implementations of automata learning algorithms.

Algorithm Resources Proofs Automata
L* Angluin, 1987, Lecture Notes Lstar DFA, Moore, Mealy
NL* Bollig et al., 2009 NLstar.v NFA
Kearns-Vazirani Kearns-Vazirani, 1994, Balle, 2010 KV DFA, Moore, Mealy
TTT Isberner et al., 2014 TTT DFA, Moore, Mealy

These notes summarize each of the main proof arguments and algorithm designs.

Functions return sigma types, so each sub-component of each algorithm provides a proof of correctness alongside its computational outputs.

Layout

  • automata - definitions for alphabets, regular languages, and automata, including the correctness properties of language encoding and minimality
  • algorithms - formally-verified implementations of AAL algorithms, a general-purpose implementation of Rivest-Schapire counterexample analysis used in multiple implementations
  • normalization - post-learning normalization of FSMs
  • Teacher.v - definitions for the Minimum Adequate Teacher model
  • Teacher.ml - OCaml entrypoint for using the extracted library, provides functors and module types to instantiate all of the learning algorithms

Installation

# Will install both lstar (the OCaml release) and lstar-rocq (the Rocq theory development)
opam install lstar

Building

# Install Dependencies
opam switch create rocq 5.3.0
opam pin add rocq-runtime 9.1.0
opam install rocq-prover dune

# Clone and build
git clone https://github.com/CharlesAverill/lstar-rocq && cd lstar-rocq
make # will build lstar-rocq, extract, then build lstar

Warning

By default, this project will build with ExtrOcamlNatInt, which is unsound in the event of overflow. Unless your DFAs could potentially include 2^63 states, this shouldn't be a problem. If you'd like me to support ExtrOcamlNatBigInt instead, please open an issue and I'll get on it.

Example

An example execution is provided in alternating.ml. The target language is alternating bit strings (e.g., "01", "10", "101", "0101", etc.). It can be recognized by the following four-state DFA: alternating DFA

Running dune exec dfa.alternating will start the learning algorithm, report that it has found a DFA that encodes the language, and then run some test cases for bit strings of length 3:

$ dune exec dfa.alternating
=== L* ===
DFA found
States (4):
  q0    accept <- initial
  q1    accept
  q2    accept
  q3    reject
Transitions:
  q0   --0--> q1
  q0   --1--> q2
  q1   --0--> q3
  q1   --1--> q2
  q2   --0--> q1
  q2   --1--> q3
  q3   --0--> q3
  q3   --1--> q3
DOT file at /tmp/L*_alternating8dc429.dot
Input       Expected  Got       Correct 
[000]       false     false     Y
[001]       false     false     Y
[010]       true      true      Y
[011]       false     false     Y
[100]       false     false     Y
[101]       true      true      Y
[110]       false     false     Y
[111]       false     false     Y
Accuracy: 8/8

See more examples.

mod3 DFA

div7 DFA

traffic Moore

vending Mealy

suffix DFA suffix NFA

Releases

Contributors

Languages