I left my position at Goethe University in March 2015. This page is outdated. Current information (including downloads) can be found on my main page
sore-inf is a tool that learns deterministic single occurrence regular expressions (SOREs) from positive examples. This is an implementation of the learning algorithms from the paper that Timo Kötzing and I published at ICDT 2013 (paper
, free preprint
), containing bugfixes from the upcoming journal version (mail me for a preprint).
For further explanation, see the paper. If you want to learn DTDs, use the dtd-inf
You need to install Python 3
on your computer (Python 2 will not work). Download the package
, unpack it. You can then run
python3 sore-inf.py --help
. (Depending on your system, you can give
executable rights and run it directly.)
./sore-inf.py abc acb c
Computes a deterministic SORE for the sample consisting of the words
. Note that the prettifcation algorithm uses character classes, e.g., instead of
, it writes
Right now, we only allow letters that consist of single characters. As this is a tool that is mostly directed to theorists, it would be useful to have letters like
A327, but we couldn't be bothered to implement this. (In fact, if you want to do this: most of the code already supports this, you would only need to change some parsing code in
The code has not been audited or debugged in large scale (it should work, but don't bet the farm on it). It is also not particularly optimized, neither for efficiency, nor for readability. (But it should be quite fast.) Also, same files use white space as indentation, others tabs. Sorry.
The way the prettification algorithm is used is particularly ugly: Instead of prettifying the inferred regular expression in a tree type data structure, the expression is inferred as string, which is then parsed and prettified. A nice implementation would skip the intermediate string representation. This is one of the reasons why, if your element names contain any fancy unicode stuff, something might break.
Apart from the algorithms in the paper, this implementation also uses an additional post-processing step that makes the expressions prettier (e.g., turns nested expressions like
(a|b|c|d), etc.) The language theoretic details can be found in a half-finished technical report that is available from Dominik D. Freydenberger.
Authors and license
The core inference algorithm was implemented by Dominik D. Freydenberger and uses this implementation
of Tarjan's Algorithm by Dries Verdegem (which, to our knowledge, is in the public domain). The prettification algorithm is a part of the M.O.D.O.D.
library, which was designed (only for DREs) by Dominik D. Freydenberger
and implemented by Christoph Burschka
. The creation of the M.O.D.O.D. library was generously supported by the program "Nachwuchswissenschaftler/innen im Fokus" (Goethe University). We put this stuff under the MIT License, and the source code is already included.
last modified: Wed Jan 13 16:39:43 2016 by Dominik D. Freydenberger