Getting Started with Cora

(version 13/02/2019)

A short, but necessary, presentation of Awali.

Awali is written in C++ and is organised into three layers: the static, the dynamic, and the interface layers.

The core of the platform is the static level, which provides the data structures and a library of algorithms. The type of a weighted automaton -- called the context -- is determined by the type of weights and the type of labels. Every algorithm is implemented via template functions working on template classes, and is compiled for the type of automata that are used. Efficiency is partly based upon this generic programming which is anyway essential when dealing with weighted automata.

The dynamic level allows both the call of functions of the static level and genuine C++ programming with the use of a kind of universal type of automata. This type is an abstraction of template (static) types of automata; it gives access to a complete template-free API for weighted automata. A remarkable feature of the dynamic level is the on-request compilation of modules (data structures and algorithms) from the static level. Even written at the dynamic level, programs are compiled and not interpreted at execution time.

The interface level offers for the time being two kinds of access to the lower layers: a command-line interface, called Cora, which allows the call to most of the algorithms of the static level, and a Python interface to both the dynamic and the static levels.

The easiest way to begin with Awali platform is probably to play with the command-line module Cora.

What is at hand

After Awali installation, the command

In [ ]:
!cora help

yields the list of available commands (89, without counting the options we'll explain below).

$ cora help <command>

donne un peu plus d'informations sur la commande <command>, eg:

In [2]:
!cora help determinize

Determinize an NFA. The result may be not complete.
Usage : determinize <aut>

The command

In [ ]:
!cora list

yields the list of preloaded automata that are part of Awali distribution (11 presently).

The first command

A quite natural way to get used with Cora commands is to apply them on preloaded automata and, to begin with, with preloaded Boolean automata. For instance the command:

In [4]:
!cora info a1

Compiling module "context" for a new automaton context (lal_char_b)
Linking module "context" for a new automaton context (lal_char_b)

 Weights : B	Alphabet : { a, b }

3 state(s)        	6 transition(s)
1 initial state(s)	1 final state(s)

yields informations (number of states, of transitions, etc.) on the automaton a1.

The two lines displayed before this output explain what is going on during the waiting time. Awali is installed without that any function at the static level be compiled. When the first function is called or, later, when a function that has not been compiled yet is called, Awali recognises it, launches the compilation of a group of functions (a module) for the "type" of the automaton that is used by the command (the context), create the corresponding links, and executes the command.

If the same command is repeated, the answer is immediate (unless the computation time is noticeable) as Awali will have recognised that the necessary function is already compiled. In what follows, we will not show these messages anymore. The "context" will be explained below (or not).

In [1]:
!cora display a1

opens a pdf viewer which display a graphical representation of a1 generated by Graphviz.

Some classical functions

In [2]:
!cora determinize a1 > a1det.json

computes the determinisation of a1 and stores it, under json format, in the file a1det.json. This automaton that is just created (and which is stored in the current directory) can be called as an operand by any other command.

In [3]:
!cora -Na1det display a1det.json

displays a1det in another window. Thanks to option -N, this window holds the name a1det; without it, the window's name would have been tmp and this window would have replaced the preceding one.

In [4]:
!cora min-quotient a1det.json \| display -

computes the minimal quotient of a1det and displays it in the window tmp.

This line shows how it is possible to chain commands in Cora by means of a kind of "fake pipe" : the result of the first command is sent to the seconde one which receive it by means of the -.

For instance, Brzozowski's method for the computaion of the minimal automaton of the language accepted by an automaton may be written (on one line):

In [5]:
!cora transpose a1 \| determinize - \| transpose - \| determinize - \| display -

Awali of course implements Kleene Theorem and produce a rational (regular) expression from an automaton:

In [6]:
!cora aut-to-exp a1

(a+b)*(ab)(a+b)*

The method used to compute the expression is the state elimination method (is there really another one?) together with an elementary, natural, and efficient heuristic.

Construction of automata

A first method to constructing an automaton is to use the converse part of Kleene Theorem:

In [7]:
!cora exp-to-aut '(a+b)*(ab)(a+b)*' \| display -

The method used to building this automaton is the one of derived terms, that is the automaton obtained is the one often called Antimirov automaton. Using options, one can also build, with the standard method, the standard automaton of the expression, also called Glushkov or position automaton, which has obviously 7 states:

In [8]:
!cora -Mstandard exp-to-aut '(a+b)*(ab)(a+b)*' \| display -

or the Thompson automaton with the thompson method:

In [9]:
!cora -Mthompson exp-to-aut '(a+b)*(ab)(a+b)*' \| display -

The alphabet on which the automaton is built is implicitely the set of letters that occur in the rational expression that is considered. It could be conceived that the alphabet is indeed strictly larger, as in the following example where the option -A allows to specify the alphabet explicitely:

In [10]:
!cora -Aabc exp-to-aut '(a+b)*(ab)(a+b)*' \| display -

The result is not different from the one obtained before. The difference appears when one tries to make the automaton complete:

In [11]:
!cora -Aabc exp-to-aut '(a+b)*(ab)(a+b)*' \| complete - \| display -

Another method for building automata with Cora consists in using the edit command in order to add, or suppress, states, or transitions, to an automaton that already exists:

$ cora edit a1

or the create command to build an automaton from scratch -- with the specification of the alphabet if the default one A={a,b} is not sufficient:

$ cora -Aabcd create

These two commands open an interactive session in the terminal.

Other commands

Cora offers a large number of commands, the name of which are self-explanatory in general. In particular, it accepts all commands present in Grail or in Fado.

Notice the difference between

$ cora minimal-automaton <aut>

which computes the minimal automaton of the language accepted by the (Boolean) automaton <aut> and

$ cora min-quotient <aut>

which computes le minimal quotient of <aut> (also called minimal bisimulation).

Input--Output

The automata created with Cora (or Awali), and those which are preloaded, are stored under json format (hence the extension in the above examples). Remark that no extension is used for calling preloaded automata, it is the way they are distinguished from others.

One can write an automaton under that json format with the cat command:

In [ ]:
!cora cat a1

Cora, and Awali, output, and read automata written under other description formats, namely those used by the Grail and Fado platforms (for Boolean automata only):

In [12]:
!cora -Ograil cat a1

(START) |- s0
s0 a s0
s0 a s1
s0 b s0
s1 b s2
s2 a s2
s2 b s2
s2 -| (FINAL)

Rational expressions can be read, and output, under a text or a jsonformat. Under the text format, they are written between quotes (for input). In order to be input from a file, they should necessarily be stored under the json format.

In [13]:
!cora catE 'a+b'

a+b
In [14]:
!cora -Ojson catE 'a+b' > e.json
!cora -Ijson catE  e.json       

a+b

Further features of Cora, in particular the computations with weighted automata and with transducers, will be treated in other notebooks and pieces of documentation.