This tool addresses the regular language synthesis problem, for a target language (ie set of finite words) satisfying some constrained horn clauses.
The tool takes as an input an SMT2 file containing:
- A declaration of an uninterpreted language, actually an interpreted function from words to booleans
- A series of constrained horn clauses: each of these formula starts with
a series of string variables universally quantified, followed by an
implication: the premise may contain some string constrains on the
variables, alongside one (or more) occurrence(s) of the uninterpreted predicate.
The conclusion of the implication is either
falseor another occurrence of the uninterpreted predicate.
The goal is then to synthesize a suitable set of words for the uninterpreted predicate. The tool aims at the synthesis of a regular set, that is to say a language recognized by a deterministic finite automaton (DFA). Two methods are currently implemented:
- SAT-based learning: a DFA is extracted from the model of a SAT-problem. this DFA is then checked against each clause, looking for falsifying example. If none is found, the DFA is returned. Otherwise, the counterexample is embedded back in the SAT specification.
- L*-based learning: the check above qualifies as an equivalence query in the active learning terminology. Additionally, the L* algorithms produces membership queries. These are answered by instantiating clauses with specific values.
-
For SAT based:
python3 src/main.py models/smt2/linear/monadic/one_token_pass.smt2 -
For L*:
python3 src/main.py models/smt2/linear/monadic/one_token_pass.smt2 --solver z3-noodler --method lstar -
For SFA based:
python3 src/main.py models/smt2/linear/monadic/one_token_pass.smt2 --solver ostrich --method sfa-learning -
For local search based:
python3 src/main.py models/smt2/linear/monadic/one_token_pass.smt2 --solver ostrich --method ls -
For pcp benchmark generation where pcp_name includes 23hard, hard, instance, and pcp43:
python3 src/pcp_parser.py {pcp_name} -
More options:
./src/chc.py --help
example:
python experiments/run_experiments.py --problem-set models/smt2/linear/ --exp-cfg experiments/experiments_config.json --method sfa-learning --chc-solver ostrich --linear
We make use of python's match/case which is not available for python versions before 3.10.
The following dependencies can be installed by pip3 install -r requirements.txt
The path to different binaries and other configurations is read from the file ./config.json
that is NOT in the repository as it is system dependent.
However, a default example configuration is located at ./config.sample.
Tip: Create a file ./config.json with the contents of ./config.sample and
adjust the values (paths) accordingly.
Tests are in the tests directory.
Run them with:
pytest
or
python -m unittest discover tests
from the root directory
In addition to the previous dependencies, some SMT2 solver should be installed. This solver must be available from the command line, to perform SMT2 interactive and incremental queries.
The paths to the binaries should be in ./config.json.
On Ubuntu/Debian, one can simply install the z3 package with
sudo apt install z3
Download and install it from the github repository
On Ubuntu/Debian, one can simply install the cvc4 package with
sudo apt install cvc4