ASTL

Pourquoi ASTL

par ce que ca m'ammuse
car il est delicat de programmer des algorithmes sur automates
car il n'existe pas de bonne librairies sur les automates
car je connais un certain nombre de techniques sur l'implementation des automates
car le code optenu est asser bon (proche du code C ! au niveau efficacite memoire & temps)

ASTL est une librairie generique sur les automates
http://www-igm.univ-mlv.fr/~lemaout/ASTL/main.html

Dans ASTL nous cherchons a definir un ensemble d'interfaces comme celle de container ainsi qu'un ensemble d'iterateurs sur ces containers afin de pouvoir ecrire une librairie d'algorithmes sur les automates

La structure generale

La structure generale voulue est la suivante, en effet il nous est apparu neccessaire de produire differentes implementation d'automates pour optenir de bon comportement au niveau de la complexite
et de l'efficacite.

Interface for DFAs

The interface on the automaton class in ASTL is willingly limited to some very basic operations to allow maximal flexibility and to minimize the amount of work when creating a new automaton class.

template <class sigma, class tag>
class DFA_*
{ 
public:
  typedef sigma Sigma;
  typedef tag Tag;
  typedef sigma::Alphabet Alphabet;
  typedef State;
  typedef Edges;

  State        new_state();
  void         set_trans(State from, Alphabet a, State to);
  void         del_trans(State s, Alphabet a);
  void         change_trans(State s, Alphabet a, State new_aim);
  void         del_state(State s);
  void         copy_state(State from, State to);
  State        duplicate_state(State s);
  State        delta1(State s, Alphabet a) const;
  const Edges& delta2(State s) const;
  Tag&         tag(State s);
  void         initial(State s);
  State        initial() const;
  void         read(istream &in);
  void         write(ostream &out) const;
  iterator     begin();
  iterator     end();

`new_state`^*	Returns a handler on a freshly allocated state.
`set_trans`^*	Adds a transition between states `from` and `to` with the letter `a`.
`del_trans`^*	Removes the transition with letter `a` from state `s`.
`change_trans`^*	Redirects the transition with letter `a` of state `s` toward state `new_aim`.
`del_state`^*	Removes state `s`.
`copy_state`^*	Overwrites state `to` with state `from`.
`duplicate_state`^*	Allocates a new state and copies state `s` into it. Semantically equivalent to `dfa.copy_state(s, dfa.new_state());`
`delta1`	Returns the aim of transition with letter `a` of state `s`. If the transition is undefined, returns the value `dfa.null_state`.
`delta2`	Returns the set of all outgoing transitions of state `s`.
`tag`	Returns a reference on the tag of state `s`.
`initial(State)^*`	Sets the initial state to `s`.
`initial()`	Returns the initial state or `dfa.null_state` if undefined.
`read`	Reads the automaton from binary stream `in`.
`write`	Writes the automaton to binary stream `out`.
`begin`	Returns an iterator on the first state of Q.
`end`	Returns a past-the-end iterator on Q.

un exemple :

// File: buildic.cc

// Copyright: Dominique REVUZ

// Date: Thu Dec 11 1997

// Description: Construction of an automaton

// from a set of strings in (cin)

#include <iostream.h>
#include <String.h>
#include <iterator.h>
#include <dfa_map.hh>
#include <dfalgo_trie.hh>
#include <dfalgo_lang.hh>
#include "dfalgo_online_minimal.hh"
#include "tag_buildic.hh"
#include "alpha_buildic.hh"

#include <dfalgo_mini.hh>

typedef
DFA_map<alpha_buildiçag_buildic > automates_buildic;

int
main(int argc, char *argv[])
{
automates_buildic A;
istream_iterator<vector<automates_buildic::Alphabet> > debut(cin);
istream_iterator<vector<automates_buildic::Alphabet> > fin;

build_tree_from_vectors(A, debut,fin );

cout << A.state_count() <<' '<< A.trans_count() << endl ;

acyclic_minimization(A);
cout << A.state_count() <<' '<< A.trans_count() << endl ;

language(A,ostream_iterator<unsigned char>(cout));
exit(0);
}

un exemple idiot creation d'un arbre dans une structure d'automate minimisation de l'arbre et affichage du language reconu.
Version pour bientot construction direct de l'automate minimal.
Version pour hier manipulation de grammaires et applications sur des textes.
Version pour avant-hier manipulation de dictionnaires et de textes.

objectifs :

algo de manipulation standard d'automates

acycliques deterministes / non determninistes
deterministes / non determninistes
automates a piles et piles cactus

algo de traitement de textes

pattern matching (nombreuses implementations realise)
manipulation de grammaires
applications de grammaires

algo sur les monoides

vous me dite ce qu'il faut