Article

Introducing VAUCANSON

Authors:

Sylvain Lombardy,

Yann Régis-Gianas,

Jacques SakarovitchAuthors Info & Claims

CIAA'03: Proceedings of the 8th international conference on Implementation and application of automata

Pages 96 - 107

Published: 16 July 2003 Publication History

Abstract

This paper reports on a new software platform called Vaucanson and dedicated to the computation with automata and transducers. Its main feature is the capacity of dealing with automata whose labels may belong to various algebraic structures.

The paper successively shows how Vaucanson allows to program algorithms on automata in a way which is very close to the mathematical expression of the algorithm, describes some features of the Vaucanson platform, including the fact that the very rich data structure used to implement automata does not weigh too much on the performance and finally explains the main choices of the programming design that enable to achieve both genericity and efficiency.

References

[1]

A. Arnold, A. Dicky, and M. Nivat, A note about minimal non-deterministic automata, Bull. EATCS 47 (1992), 166-169. 97

[2]

J.-M. Champarnaud and D. Ziadi, Canonical derivatives, partial derivatives and finite automaton constructions, Theor. Comp. Sci. 289 (2002), no. 1, 137-163. 103

Digital Library

[3]

J.H. Conway, Regular algebra and finite machines, Chapman and Hall, 1971. 97

[4]

J. Darbon, T. Géraud, and A. Duret-Lutz, Generic implementation of morphological image operators, Int. Symp. on Mathematical Morphology VI (ISMM'2002), April 2002, pp. 175-184. 105

[5]

A. Duret-Lutz, T. Géraud, and A. Demaille, Design patterns for generic programming in C++, Proc. of the 6th USENIX Conf. on Object-Oriented Technologies and Systems (COOTS'01), USENIX Association, 2001, pp. 189-202. 106

Digital Library

[6]

A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr, On the design of CGAL, the computational geometry algorithms library, Tech. Report 3407, INRIA, April 1998. 105

[7]

E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design patterns: Abstraction and reuse of object-oriented design, LNCS 707 (1993), 406-431. 103, 106

Digital Library

[8]

J. Hopcroft and J. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979. 98, 102

Digital Library

[9]

S. Lombardy, On the construction of reversible automata for reversible languages, Proc. of ICALP'02, LNCS 2380 (2002), 170-182. 97, 98

Digital Library

[10]

S. Lombardy and J. Sakarovitch, Star height of reversible languages and universal automata, Proc. of LATIN'02, LNCS 2286 (2002), 76-89. 97

Digital Library

[11]

S. Lombardy and J. Sakarovitch, Vaucanson-G, A package for drawing automata and graphs, http://www.liafa.jussieu.fr/~lombardy/Vaucanson-G/, 2002. 96

[12]

S. Lombardy and J. Sakarovitch, On the star height of rational languages, a new presentation for two old results, World Scientific (to appear). 97

[13]

V. Le Maout, Cursors, Proc. of CIAA 2000, LNCS 2088 (2001), 195-207. 104

Digital Library

[14]

O. Matz, A. Miller, A. Potthoff, W. Thomas, E. Valkema, The Program AMoRE, http://www-i7.informatik.rwth-aachen.de/d/research/amore.html, RWTH Aachen, 1995. 101

[15]

O. Matz and A. Potthoff, Computing small nondeterministic finite automata, proc. of TACAS'95, BRICS Notes Series, 1995, pp. 74-88. 97

[16]

M. Mohri, F. C.N. Pereira, and M. Riley, General-purpose Finite-State Machine Software Tools, http://www.research.att.com/sw/tools/fsm/, AT&T Labs - Research, 1997. 97, 101

[17]

D.R. Musser and A.A. Stepanov, Algorithm-oriented generic libraries, Software - Practice and Experience 24 (1994), no. 7, 623-642. 105

Digital Library

[18]

G. van Noord, Finite State Automata Utilities, http://odur.let.rug.nl/~vannoord/Fsa/, 2000. 97

[19]

J. Sakarovitch, Éléments de théorie des automates, Vuibert, 2003. 98, 102

Cited By

Demaille ADuret-Lutz ALombardy SSakarovitch J(2013)Implementation concepts in vaucanson 2Proceedings of the 18th international conference on Implementation and Application of Automata10.1007/978-3-642-39274-0_12(122-133)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39274-0_12
Borghi ADavid VDemaille A(2006)C-TransformersXRDS: Crossroads, The ACM Magazine for Students10.1145/1144366.114436912:3(3-3)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1145/1144366.1144369
Stroppa NYvon FDagan IGildea D(2005)An analogical learner for morphological analysisProceedings of the Ninth Conference on Computational Natural Language Learning10.5555/1706543.1706565(120-127)Online publication date: 29-Jun-2005
https://dl.acm.org/doi/10.5555/1706543.1706565
Show More Cited By

Introducing VAUCANSON
1. Theory of computation

Recommendations

Introducing VAUCANSON
Implementation and application of automata

This paper reports on a new software platform called VAUCANSON and dedicated to the computation with automata and transducers. Its main feature is the capacity of dealing with automata whose labels may belong to various algebraic structures.The paper ...
Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata

Two ways of introducing alternation for context-free grammars and pushdown automata are compared. One is the usual way which combines “states” with alternation [1], [4], [7], and the other is the way used in [6] to define the alternating context-free ...
Inside vaucanson
CIAA'05: Proceedings of the 10th international conference on Implementation and Application of Automata

This paper presents some features of the Vaucanson platform. We describe some original algorithms on weighted automata and transducers (computation of the quotient, conversion of a regular expression into a weighted automaton, and composition). We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CIAA'03: Proceedings of the 8th international conference on Implementation and application of automata

July 2003

312 pages

ISBN:3540405615

Editors:
Oscar H. Ibarra
University of California, Department of Computer Science, Santa Barbara, CA
,
Zhe Dang
Washington State University, School of Electrical Engineering and Computer Science, Pullman, WA

Sponsors

Graduat Division, University of California, Santa Barbara
Computer Science Department, University of California, Santa Barbara
College of Engineering, University of California, Santa Barbara
Expertcity, Inc.
AT&T: AT&T Labs Research

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 16 July 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Demaille ADuret-Lutz ALombardy SSakarovitch J(2013)Implementation concepts in vaucanson 2Proceedings of the 18th international conference on Implementation and Application of Automata10.1007/978-3-642-39274-0_12(122-133)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39274-0_12
Borghi ADavid VDemaille A(2006)C-TransformersXRDS: Crossroads, The ACM Magazine for Students10.1145/1144366.114436912:3(3-3)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1145/1144366.1144369
Stroppa NYvon FDagan IGildea D(2005)An analogical learner for morphological analysisProceedings of the Ninth Conference on Computational Natural Language Learning10.5555/1706543.1706565(120-127)Online publication date: 29-Jun-2005
https://dl.acm.org/doi/10.5555/1706543.1706565
Sakarovitch J(2005)The language, the expression, and the (small) automatonProceedings of the 10th international conference on Implementation and Application of Automata10.1007/11605157_2(15-30)Online publication date: 27-Jun-2005
https://dl.acm.org/doi/10.1007/11605157_2

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents