ASTL

Pourquoi ASTL

  1. par ce que ca m'ammuse
  2. car il est delicat de programmer des algorithmes sur automates
  3. car il n'existe pas de bonne librairies sur les automates
  4. car je connais un certain nombre de techniques sur l'implementation des automates
  5. 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 :

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 :

  1. algo de manipulation standard d'automates
    1.  acycliques deterministes / non determninistes
    2. deterministes / non determninistes
    3. automates a piles et piles cactus
  2. algo de traitement de textes
    1. pattern matching (nombreuses implementations realise)
    2. manipulation de grammaires
    3. applications de grammaires
  3. algo sur les monoides
    1. vous me dite ce qu'il faut