
Autograph is now part of
TRAG


What is Autograph
Autograph is a project carried out at the
LaBRI
(Laboratoire Bordelais de Recherche en Informatique)
at the University of Bordeaux.
Autograph is an experimental tool written in Common Lisp
for verifying properties of graphs of bounded cliquewidth.
It is written in Steele Bank Common Lisp ( SBCL).
It uses the Autowrite library which provides the operations needed to create
and manipulate automata.
The following famous theorem connects the problem
of verifying graph properties with term automata.
Theorem
Monadic secondorder model checking is
for treewidth [Courcelle (1990)]
and cliquewidth [Courcelle, Makowski, Rotics (2001)].
Treewidth and cliquewidth are graph complexity measures based
on graph decompositions.
A decomposition produces a term representation of the graph.
For a graph property expressed in monadic second order logic (MSO),
the algorithm verifying the property
takes the form of a term automaton which recognizes the terms
denoting graphs satisfying the property.
Main features of Autograph
Basic automata for graph properties
 Singleton()
 edge(X1,X2)
 subset(X1,X2)
 equality(X1,X2)
Polynomial
 Stable()
 Partition(X1,...Xn)
 kcardinality()
Non polynomial
 kColoring(C1,...,Cn) compilable up to cwd=4 (for k=3)
 Connectedness() compilable up to cwd=3
 Clique() compilable up to cwd=4
 Path(X1,X2) compilable up to cwd=4
 Acyclic() not compilable
Combination of previous automata (non polynomial)
 kColorability() compilable up to k=3 (cwd=2), k=2 (cwd=3)
 AcyclicColorability() not compilable (uses Acyclic)
 kChordFreeCycle()
 kMaxDegre()
 kVertexCover()
 Composition of automata
 homomorphisms and inversehomomorphisms
 determinization
 reduction and minimization (for tableautomata only)
 boolean operations (union, intersection, complementation)
Obtaining Autograph
Autograph is now part if the TRAG project (Term Rewriting Automata and Graphs)
available on BitBucket:
git clone https://idurand@bitbucket.org/idurand/trag.git
Contact information
Should you have any comments or suggestions regarding Autograph,
or ideas on new functionalities that you would like to see in future
releases of Autograph, please send them to
idurand@labri.fr.
Bibliography
B. Courcelle.
Graph Structure and Monadic SecondOrder Logic. 2011
Cambridge University Press
B. Courcelle and I. Durand.
Verifying monadic second order graph properties with tree automata.
Proceedings of the 3rd European Lisp Symposium, pages 721, 2010
I. Durand.
Implementing huge term automata.
Submitted to the 4th European Lisp Symposium, 2011.
Pointers to relevant sites
Here are some pointers to other sites with similar interests,
listed by topic.
Sites and people

Steele Bank Common Lisp (SBCL)
Irčne Durand
Bruno Courcelle