Implement efficient automata and regular languages

[sagetrac-mercatp]

Define a class DetAutomaton that permits to manipulate deterministic automata, and a class CAutomaton for non-deterministic automata. It implement efficient operations writted in C language to manipulate automata and regular languages.

a class DetAutomatonGenerators is usefull to generate easily DetAutomaton.

The ticket has bee refactore and is in now in a correct situation with doc test, documentation in thematic tutorial.

This ticket is necessary to for the ticket b-adic and the usage of its tools

CC: @seblabbe @videlec @dkrenn

Component: packages: standard

Keywords: automata, regular languages

Author: Paul Mercat, Dominique Benielli

Branch/Commit: public/implement_efficient_automata_and_regular_languages @ ee2753d

Issue created by migration from https://trac.sagemath.org/ticket/25041

[sagetrac-dbenielli]

Branch: u/dbenielli/implement_efficient_automata_and_regular_languages

[sagetrac-git]

Commit: 7d3215a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7d3215a

automaton ticket

[sagetrac-mercatp]

Changed branch from u/dbenielli/implement_efficient_automata_and_regular_languages to u/mercatp/implement_efficient_automata_and_regular_languages

[sagetrac-git]

Changed commit from 7d3215a to d37f6ad

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d37f6ad

Add the last changes made in sage-8.1 (the version merged in sage-8.3.beta2 was not the last one).

[sagetrac-dbenielli]

Changed branch from u/mercatp/implement_efficient_automata_and_regular_languages to u/dbenielli/implement_efficient_automata_and_regular_languages

[fchapoton]

comment:7

You should look at the patchbot report, and fix everything wrong..

---

New commits:

29bde5f	small typo
bb7f446	Merge branch 'u/mercatp/implement_efficient_automata_and_regular_languages' of git://trac.sagemath.org/sage into t/25041/implement_efficient_automata_and_regular_languages
7854c83	small change for doc
86fe4be	small change for doc
814f67d	Merge branch 'u/mercatp/implement_efficient_automata_and_regular_languages' of git://trac.sagemath.org/sage into t/25041/implement_efficient_automata_and_regular_languages

[fchapoton]

Changed commit from d37f6ad to 814f67d

[sagetrac-git]

Changed commit from 814f67d to 43429fd

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d39d1e0	for test
43429fd	bigger alphabet to check

[sagetrac-mercatp]

Changed branch from u/dbenielli/implement_efficient_automata_and_regular_languages to u/mercatp/implement_efficient_automata_and_regular_languages

[sagetrac-git]

Changed commit from 43429fd to 74e9cf7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

74e9cf7

Correct errors in doctests and doc.

[sagetrac-dbenielli]

Changed branch from u/mercatp/implement_efficient_automata_and_regular_languages to u/dbenielli/implement_efficient_automata_and_regular_languages

[sagetrac-mercatp]

Changed branch from u/dbenielli/implement_efficient_automata_and_regular_languages to u/mercatp/implement_efficient_automata_and_regular_languages

[sagetrac-dbenielli]

Changed branch from u/mercatp/implement_efficient_automata_and_regular_languages to u/dbenielli/implement_efficient_automata_and_regular_languages

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4252638

reduce size doc

[sagetrac-git]

Changed commit from 74e9cf7 to 4252638

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4e7aabc

typo

[sagetrac-git]

Changed commit from 4252638 to 4e7aabc

[sagetrac-mercatp]

Changed branch from u/dbenielli/implement_efficient_automata_and_regular_languages to u/mercatp/implement_efficient_automata_and_regular_languages

[seblabbe]

comment:75

The branch does not apply anymore on the most recent development version of Sage.

I use the occasion to share some thoughts about this ticket. This is not the first time that a ticket is created to add a ton of new lines of code into Sage and in too many of those cases, the code just became dead on the sage trac for a ton of different reasons that I will not enumerate here (#21295, #16110, #12224 are examples which are taking years to complete). Therefore, now, I want to make sure that this does not happen again with this ticket since I am very interested in having a fast implementation of automaton available in Sage.

While I think that it is a very good idea that this ticket eventually gets merged into Sage, I would like to suggest to the authors of this ticket to consider the possibility of creating an independent Python Package containing this code beside this ticket. To me, this would be benefical for many reasons:

• Python Package are easy to install, use and maintain.
• If some important modifications that are backward incompatible are to be done in your code in the next two years, then no one will bother.
• In Sage, code modification must be backward compatible. This means that you will lose a lot of time in adding deprecation warning to your code in the next years. Also, this means that you have to lose a lot of time right now while thinking about all the different use cases that people you don't know may have during using your code.
• To me, the creation of a Python Package is a good way of making a new module go into Sage. Being use publically for one or two years as a Python Package before being included into Sage allows to be sure about the proper interface and without losing much time thinking about how other will use your code.
• This is what I ended up doing for Add a cython implementation of the Kolakoski word #13346, Generation of Double square tiles #13069 and Add file sage/misc/latex_standalone.py and class TikzPicture #20343. Instead of waiting years for a review, I decided to put those module into my own python package (slabbe). And the day someone tells me that some of my code is interresting enough for others, then I will consider updating the ticket with the most recent version of the desired module. Meanwhile, I will not update my code at two places in parallel. The most recent version is in my package and slowly, it converges to something usable for many usage.
• In the next two years, the code base of Sage may change and this can break the application the branch of this ticket (like right now today!), which makes your code unusable, untestable.

Here are examples of Python packages for Sage:

• https://pypi.org/project/surface_dynamics/ (include Python, Cython, and C code)
• https://pypi.org/project/slabbe/ (includes Cython code)
• https://pypi.org/project/train-track/ (that you know)
• https://github.com/miltminz/EkEkstar (simple: on single Python file)
• https://github.com/sagemath/sage_sample (a demo with uptodate travis setup, etc.)

Good luck:)

[sagetrac-git]

Changed commit from de8830b to 6ce5473

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

ca9819b	doc fail
85a6ce5	link ok
e582064	last fix for pdf generation
151fc61	Merge branch 'public/b-adic' of git://trac.sagemath.org/sage into t/21072/public/b-adic
46a45d7	Add doc in the thematic tutorial about Automtat and regular languages.
18e8588	scale
c21c045	Correct the thematic tutorial about automata and regular languages, and correct a little bug with DetAutomaton.plot().
79d2c3c	Merge branch 'public/b-adic' of git://trac.sagemath.org/sage into public/b-adic
6d6356c	sdl .h librairy
6ce5473	ticket automaton from -adic

[videlec]

comment:78

This is certainly not a package: http://doc.sagemath.org/html/en/developer/packaging.html

[videlec]

comment:79

Are the two methods get_automatonc and get_Automaton the only things you will do to make the current Sage code and your code interact?

[videlec]

comment:80

If you intend to include your Python code in Sage sources then

• all method names must be lower case with as few abbreviations as possible (e.g. proji is not acceptable)
• all class names must be CAML case with as few abbreviations as possible (e.g. DetAutomaton should be DeterministicAutomaton)
  This is not an especially nice convention, but this is how it is.

[videlec]

comment:81

Why ON PLACE in the documentation of permut_op in upper case? What does on place mean? Do you want to say inplace?

[videlec]

comment:82

Your usage of sig_on/sig_off is very wrong. For example, the function getDict2 contains Python code on its first line

    A = list(A)

However, you wrote in the code of the method duplicate

        sig_on()
        dC = getDict2(d, self.A, d1=d1)
        sig_off()

As written in the cysignals documentation, the code between sig_on/sig_off should not contain any Python code.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7cb0a09

fix sig_on sig_off

[sagetrac-git]

Changed commit from 6ce5473 to 7cb0a09

[sagetrac-git]

Changed commit from 7cb0a09 to 706ca78

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

706ca78

fix sig_on sig_off

[sagetrac-git]

Changed commit from 706ca78 to 0c03f34

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0c03f34

change name DetAutomaton to DeterministicAutomaton

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4c341bc

Change name "succ" to "successor". Check that the module BetaAdic exists in function WordMorphism.DumontThomas().

[sagetrac-git]

Changed commit from 0c03f34 to 4c341bc

[sagetrac-git]

Changed commit from 4c341bc to 5201b04

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

837d77e	Merge branch 'develop' into public/implement_efficient_automata_and_regular_languages
cef8a1d	dumont thomas update
5201b04	dumont thomas update

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

598383b	Merge branch 'develop' into t/25041/public/implement_efficient_automata_and_regular_languages
6cf74d5	Merge branch 'public/implement_efficient_automata_and_regular_languages' of git://trac.sagemath.org/sage into t/25041/public/implement_efficient_automata_and_regular_languages
c0ab4e9	Correct a little problem.

[sagetrac-git]

Changed commit from 5201b04 to c0ab4e9

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ee2753d

Rename methods in cautomata.pyx in order to avoid shortcuts. Correct a little thing to avoid a bud of DiGraph.edges().

[sagetrac-git]

Changed commit from c0ab4e9 to ee2753d