%global _empty_manifest_terminate_build 0
Name: python-dfa-identify
Version: 3.9.1
Release: 1
Summary: Python library for identifying (learning) DFAs (automata) from labeled examples.
License: MIT
URL: https://github.com/mvcisback/dfa-identify
Source0: https://mirrors.nju.edu.cn/pypi/web/packages/40/ec/355b1cfbe98e9cc560d60b5fd3835b232c0ad20f7e0046d8d39ad7012dd8/dfa_identify-3.9.1.tar.gz
BuildArch: noarch
Requires: python3-attrs
Requires: python3-networkx
Requires: python3-funcy
Requires: python3-bidict
Requires: python3-sat
Requires: python3-dfa
Requires: python3-more-itertools
%description
# dfa-identify
Python library for identifying (learning) minimal DFAs from labeled examples
by reduction to SAT.
[](https://cloud.drone.io/mvcisback/dfa-identify)
[](https://badge.fury.io/py/dfa-identify)
[](https://opensource.org/licenses/MIT)
**Table of Contents**
- [Installation](#installation)
- [Usage](#usage)
- [Encoding](#encoding)
- [Goals and related libraries](#goals-and-related-libraries)
# Installation
If you just need to use `dfa`, you can just run:
`$ pip install dfa`
For developers, note that this project uses the
[poetry](https://poetry.eustace.io/) python package/dependency
management tool. Please familarize yourself with it and then
run:
`$ poetry install`
# Usage
`dfa_identify` is centered around the `find_dfa` and `find_dfas` function. Both take in
sequences of accepting and rejecting "words", where are word is a
sequence of arbitrary python objects.
1. `find_dfas` returns all minimally sized (no `DFA`s exist of size
smaller) consistent with the given labeled data.
2. `find_dfa` returns an arbitrary (first) minimally sized `DFA`.
The returned `DFA` object is from the [dfa](https://github.com/mvcisback/dfa) library.
```python
from dfa_identify import find_dfa
accepting = ['a', 'abaa', 'bb']
rejecting = ['abb', 'b']
my_dfa = find_dfa(accepting=accepting, rejecting=rejecting)
assert all(my_dfa.label(x) for x in accepting)
assert all(not my_dfa.label(x) for x in rejecting)
```
Because words are sequences of arbitrary python objects, the
identification problem, with `a` ↦ 0 and `b` ↦ 1, is given below:
```python
accepting = [[0], [0, 'z', 0, 0], ['z', 'z']]
rejecting = [[0, 'z', 'z'], ['z']]
my_dfa = find_dfa(accepting=accepting, rejecting=rejecting)
```
# Minimality
There are two forms of "minimality" supported by `dfa-identify`.
1. By default, dfa-identify returns DFAs that have the minimum
number of states required to seperate the accepting and
rejecting set.
2. If the `order_by_stutter` flag is set to `True`, then the
`find_dfas` (lazily) orders the DFAs so that the number of
self loops (stuttering transitions) appearing the DFAs decreases.
`find_dfa` thus returns a DFA with the most number of self loops
given the minimal number of states.
# Encoding
This library currently uses the encodings outlined in [Heule, Marijn JH, and Sicco Verwer. "Exact DFA identification using SAT solvers." International Colloquium on Grammatical Inference. Springer, Berlin, Heidelberg, 2010.](https://link.springer.com/chapter/10.1007/978-3-642-15488-1_7) and [Ulyantsev, Vladimir, Ilya Zakirzyanov, and Anatoly Shalyto. "Symmetry Breaking Predicates for SAT-based DFA Identification."](https://arxiv.org/abs/1602.05028).
The key difference is in the use of the symmetry breaking clauses. Two kinds are exposed.
1. clique (Heule 2010): Partially breaks symmetries by analyzing
conflict graph.
2. bfs (Ulyantsev 2016): Breaks all symmetries so that each model corresponds to a unique DFA.
# Goals and related libraries
There are many other python libraries that
perform DFA and other automata inference.
1. [DFA-Inductor-py](https://github.com/ctlab/DFA-Inductor-py) - State of the art passive inference via reduction to SAT (as of 2019).
2. [z3gi](https://gitlab.science.ru.nl/rick/z3gi): Uses SMT backed passive learning algorithm.
3. [lstar](https://pypi.org/project/lstar/): Active learning algorithm based L* derivative.
The primary goal of this library is to loosely track the state of the art in passive SAT based inference while providing a simple implementation and API.
%package -n python3-dfa-identify
Summary: Python library for identifying (learning) DFAs (automata) from labeled examples.
Provides: python-dfa-identify
BuildRequires: python3-devel
BuildRequires: python3-setuptools
BuildRequires: python3-pip
%description -n python3-dfa-identify
# dfa-identify
Python library for identifying (learning) minimal DFAs from labeled examples
by reduction to SAT.
[](https://cloud.drone.io/mvcisback/dfa-identify)
[](https://badge.fury.io/py/dfa-identify)
[](https://opensource.org/licenses/MIT)
**Table of Contents**
- [Installation](#installation)
- [Usage](#usage)
- [Encoding](#encoding)
- [Goals and related libraries](#goals-and-related-libraries)
# Installation
If you just need to use `dfa`, you can just run:
`$ pip install dfa`
For developers, note that this project uses the
[poetry](https://poetry.eustace.io/) python package/dependency
management tool. Please familarize yourself with it and then
run:
`$ poetry install`
# Usage
`dfa_identify` is centered around the `find_dfa` and `find_dfas` function. Both take in
sequences of accepting and rejecting "words", where are word is a
sequence of arbitrary python objects.
1. `find_dfas` returns all minimally sized (no `DFA`s exist of size
smaller) consistent with the given labeled data.
2. `find_dfa` returns an arbitrary (first) minimally sized `DFA`.
The returned `DFA` object is from the [dfa](https://github.com/mvcisback/dfa) library.
```python
from dfa_identify import find_dfa
accepting = ['a', 'abaa', 'bb']
rejecting = ['abb', 'b']
my_dfa = find_dfa(accepting=accepting, rejecting=rejecting)
assert all(my_dfa.label(x) for x in accepting)
assert all(not my_dfa.label(x) for x in rejecting)
```
Because words are sequences of arbitrary python objects, the
identification problem, with `a` ↦ 0 and `b` ↦ 1, is given below:
```python
accepting = [[0], [0, 'z', 0, 0], ['z', 'z']]
rejecting = [[0, 'z', 'z'], ['z']]
my_dfa = find_dfa(accepting=accepting, rejecting=rejecting)
```
# Minimality
There are two forms of "minimality" supported by `dfa-identify`.
1. By default, dfa-identify returns DFAs that have the minimum
number of states required to seperate the accepting and
rejecting set.
2. If the `order_by_stutter` flag is set to `True`, then the
`find_dfas` (lazily) orders the DFAs so that the number of
self loops (stuttering transitions) appearing the DFAs decreases.
`find_dfa` thus returns a DFA with the most number of self loops
given the minimal number of states.
# Encoding
This library currently uses the encodings outlined in [Heule, Marijn JH, and Sicco Verwer. "Exact DFA identification using SAT solvers." International Colloquium on Grammatical Inference. Springer, Berlin, Heidelberg, 2010.](https://link.springer.com/chapter/10.1007/978-3-642-15488-1_7) and [Ulyantsev, Vladimir, Ilya Zakirzyanov, and Anatoly Shalyto. "Symmetry Breaking Predicates for SAT-based DFA Identification."](https://arxiv.org/abs/1602.05028).
The key difference is in the use of the symmetry breaking clauses. Two kinds are exposed.
1. clique (Heule 2010): Partially breaks symmetries by analyzing
conflict graph.
2. bfs (Ulyantsev 2016): Breaks all symmetries so that each model corresponds to a unique DFA.
# Goals and related libraries
There are many other python libraries that
perform DFA and other automata inference.
1. [DFA-Inductor-py](https://github.com/ctlab/DFA-Inductor-py) - State of the art passive inference via reduction to SAT (as of 2019).
2. [z3gi](https://gitlab.science.ru.nl/rick/z3gi): Uses SMT backed passive learning algorithm.
3. [lstar](https://pypi.org/project/lstar/): Active learning algorithm based L* derivative.
The primary goal of this library is to loosely track the state of the art in passive SAT based inference while providing a simple implementation and API.
%package help
Summary: Development documents and examples for dfa-identify
Provides: python3-dfa-identify-doc
%description help
# dfa-identify
Python library for identifying (learning) minimal DFAs from labeled examples
by reduction to SAT.
[](https://cloud.drone.io/mvcisback/dfa-identify)
[](https://badge.fury.io/py/dfa-identify)
[](https://opensource.org/licenses/MIT)
**Table of Contents**
- [Installation](#installation)
- [Usage](#usage)
- [Encoding](#encoding)
- [Goals and related libraries](#goals-and-related-libraries)
# Installation
If you just need to use `dfa`, you can just run:
`$ pip install dfa`
For developers, note that this project uses the
[poetry](https://poetry.eustace.io/) python package/dependency
management tool. Please familarize yourself with it and then
run:
`$ poetry install`
# Usage
`dfa_identify` is centered around the `find_dfa` and `find_dfas` function. Both take in
sequences of accepting and rejecting "words", where are word is a
sequence of arbitrary python objects.
1. `find_dfas` returns all minimally sized (no `DFA`s exist of size
smaller) consistent with the given labeled data.
2. `find_dfa` returns an arbitrary (first) minimally sized `DFA`.
The returned `DFA` object is from the [dfa](https://github.com/mvcisback/dfa) library.
```python
from dfa_identify import find_dfa
accepting = ['a', 'abaa', 'bb']
rejecting = ['abb', 'b']
my_dfa = find_dfa(accepting=accepting, rejecting=rejecting)
assert all(my_dfa.label(x) for x in accepting)
assert all(not my_dfa.label(x) for x in rejecting)
```
Because words are sequences of arbitrary python objects, the
identification problem, with `a` ↦ 0 and `b` ↦ 1, is given below:
```python
accepting = [[0], [0, 'z', 0, 0], ['z', 'z']]
rejecting = [[0, 'z', 'z'], ['z']]
my_dfa = find_dfa(accepting=accepting, rejecting=rejecting)
```
# Minimality
There are two forms of "minimality" supported by `dfa-identify`.
1. By default, dfa-identify returns DFAs that have the minimum
number of states required to seperate the accepting and
rejecting set.
2. If the `order_by_stutter` flag is set to `True`, then the
`find_dfas` (lazily) orders the DFAs so that the number of
self loops (stuttering transitions) appearing the DFAs decreases.
`find_dfa` thus returns a DFA with the most number of self loops
given the minimal number of states.
# Encoding
This library currently uses the encodings outlined in [Heule, Marijn JH, and Sicco Verwer. "Exact DFA identification using SAT solvers." International Colloquium on Grammatical Inference. Springer, Berlin, Heidelberg, 2010.](https://link.springer.com/chapter/10.1007/978-3-642-15488-1_7) and [Ulyantsev, Vladimir, Ilya Zakirzyanov, and Anatoly Shalyto. "Symmetry Breaking Predicates for SAT-based DFA Identification."](https://arxiv.org/abs/1602.05028).
The key difference is in the use of the symmetry breaking clauses. Two kinds are exposed.
1. clique (Heule 2010): Partially breaks symmetries by analyzing
conflict graph.
2. bfs (Ulyantsev 2016): Breaks all symmetries so that each model corresponds to a unique DFA.
# Goals and related libraries
There are many other python libraries that
perform DFA and other automata inference.
1. [DFA-Inductor-py](https://github.com/ctlab/DFA-Inductor-py) - State of the art passive inference via reduction to SAT (as of 2019).
2. [z3gi](https://gitlab.science.ru.nl/rick/z3gi): Uses SMT backed passive learning algorithm.
3. [lstar](https://pypi.org/project/lstar/): Active learning algorithm based L* derivative.
The primary goal of this library is to loosely track the state of the art in passive SAT based inference while providing a simple implementation and API.
%prep
%autosetup -n dfa-identify-3.9.1
%build
%py3_build
%install
%py3_install
install -d -m755 %{buildroot}/%{_pkgdocdir}
if [ -d doc ]; then cp -arf doc %{buildroot}/%{_pkgdocdir}; fi
if [ -d docs ]; then cp -arf docs %{buildroot}/%{_pkgdocdir}; fi
if [ -d example ]; then cp -arf example %{buildroot}/%{_pkgdocdir}; fi
if [ -d examples ]; then cp -arf examples %{buildroot}/%{_pkgdocdir}; fi
pushd %{buildroot}
if [ -d usr/lib ]; then
find usr/lib -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/lib64 ]; then
find usr/lib64 -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/bin ]; then
find usr/bin -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/sbin ]; then
find usr/sbin -type f -printf "/%h/%f\n" >> filelist.lst
fi
touch doclist.lst
if [ -d usr/share/man ]; then
find usr/share/man -type f -printf "/%h/%f.gz\n" >> doclist.lst
fi
popd
mv %{buildroot}/filelist.lst .
mv %{buildroot}/doclist.lst .
%files -n python3-dfa-identify -f filelist.lst
%dir %{python3_sitelib}/*
%files help -f doclist.lst
%{_docdir}/*
%changelog
* Mon May 15 2023 Python_Bot <Python_Bot@openeuler.org> - 3.9.1-1
- Package Spec generated