[Publications]
Jean-Marc Champarnaud
Professeur à l’Université de Rouen
Laboratoire LITIS (EA 4108)
Revues avec comité de lecture
1. J.-M. Champarnaud and J.-E. Pin, A maxmin problem on finite automata, Discrete Applied Mathematics, 23(1989), pp. 91—96, pdf, ps.
2. J.-M. Champarnaud and G. Hansel, AUTOMATE, a computing package for automata and finite semigroups, Journal of Symbolic Computation, 12(1991), pp. 197—220, pdf, ps.
3. D. Ziadi, J.-L. Ponty et J.-M. Champarnaud, Passage d’une expression rationnelle à un automate fini non-déterministe, Bulletin of the Belgian Mathematical Society Simon Stevin, 4–2(1997), pp. 177—203, pdf.
4. D. Ziadi and J.-M. Champarnaud, An optimal parallel algorithm to convert a regular expression into its Glushkov automaton, Theoret. Comp. Sc., 215(1999), pp. 69—87, pdf, ps.
5. J.-M. Champarnaud, J.-L. Ponty and D. Ziadi, From Regular Expressions to Finite Automata, Intern. J. Computer Math., 72(1999), pp. 415—431, pdf, ps.
6. J.-M. Champarnaud, Subset Construction Complexity for Homogeneous Automata Position Automata and ZPC-Structures, Theoret. Comp. Sc., 267(2001), pp. 17—34, pdf, ps.
7. J.-M. Champarnaud and D. Ziadi, From C-Continuations to New Quadratic Algorithms for Automaton Synthesis, Intern. Journ. of Alg. and Comp., 11–6(2001), pp. 707—735, pdf, ps.
8. J.-M. Champarnaud and D. Ziadi, From Mirkin’s Prebases to Antimirov’s Word Partial Derivatives, Fundamenta Informaticae, 45(2001), pp. 195—205, pdf, ps.
9. J.-M. Champarnaud, Evaluation of Three Implicit Structures to Implement Nondeterministic Automata from Regular Expressions, Intern. J. of Foundations of Comp. Sc., 13–1(2002), pp. 99—113, pdf, ps.
10. J.-M. Champarnaud and D. Ziadi, Canonical Derivatives, Partial Derivatives and Finite Automaton Constructions, Theoret. Comp. Sc., 289(2002), pp. 137—163, pdf, ps.
11. J.-M. Champarnaud, G. Hansel and D. Perrin, Unavoidable Sets of Constant Length, Intern. Journ. of Alg. and Comp., 14–2(2004), pp. 241—251, pdf, ps.
12. J.-M. Champarnaud and G. Duchamp, Derivatives of rational expressions and related theorems, Theoret. Comp. Sc., 313–1(2004), pp. 31—44, pdf, ps.
13. F. Guingne, F. Nicart, J.-M. Champarnaud, L. Karttunen, T. Gaál and A. Kempe, Virtual Operations on Virtual Networks: the Priority Union, Intern. J. of Foundations of Comp. Sc., 14–6(2003), pp. 1055—1069, ps.
14. J.-M. Champarnaud et G. Hansel, Ensembles inévitables et classes de conjugaison, Bulletin of the Belgian Mathematical Society Simon Stevin, 10–5(2003), pp. 679—692, pdf, ps.
15. J.-M. Champarnaud and F. Coulon, Theoretical study and implementation of the canonical automaton, Fundamenta Informaticae, 55(2003), pp. 23—38, pdf, ps.
16. J.-M. Champarnaud, G. Hansel, T. Paranthoën and D. Ziadi, Random Generation Models for NFAs, J. of Automata, Languages and Combinatorics, 9–2/3(2004), pp. 203—216, pdf, ps.
17. J.-M. Champarnaud, F. Coulon and T. Paranthoën, Compact and Fast Algorithms for Safe Regular Expression Search, Intern. Journal Computer Math., 81–4(2004), pp. 383—401, Code source du logiciel CCP, pdf, ps.
18. J.-M. Champarnaud, F. Nicart and D. Ziadi, From the ZPC-structure of a regular expression to its follow automaton, Intern. Journ. of Alg. and Comp., 16–1(2006), pp. 17—34.
19. J.-M. Champarnaud and F. Coulon, NFA reduction algorithms by means of regular inequalities, Theoret. Comp. Sc., 327–3(2004), pp. 241—253, Erratum in Theoret. Comp. Sc., 347(2005), 437—440, pdf, pdf, ps, ps.
20. J.-M. Champarnaud, E. Laugerotte, F. Ouardi and D. Ziadi, From regular weighted expressions to finite automata, Intern. J. of Foundations of Comp. Sc., 15–5(2004), pp. 687—700.
21. J.-M. Champarnaud and T. Paranthoën, Random Generation of DFAs, Theoret. Comp. Sc., 330–2(2005), pp. 221—235, pdf, ps.
22. J.-M. Champarnaud, F. Guingne and G. Hansel, Similarity Relations and Cover Automata, RAIRO-Theoretical Informatics and Applications, 39–1(2005), pp. 115—123, pdf, ps.
23. J.-M. Champarnaud and F. Coulon, Enumerating nondeterministic automata for a given language without constructing the canonical automaton, Intern. J. of Foundations of Comp. Sc., 16–6(2005), pp. 1253—1266.
24. J.-M. Champarnaud, F. Coulon and T. Paranthoën, Brute Force Determinization of NFAs by Means of State Covers, Intern. J. of Foundations of Comp. Sc., 16–3(2005), pp. 441—451.
25. J.-M. Champarnaud, F. Guingne and G. Hansel, Cover Transducers for Functions with Finite Domain, Intern. J. of Foundations of Comp. Sc., 16–5(2005), pp. 851—865.
26. J.-M. Champarnaud, F. Ouardi and D. Ziadi, Normalized Expressions and Finite Automata, Intern. Journ. of Alg. and Comp., 17–1(2007), pp. 141—154.
27. F. Nicart, J.-M. Champarnaud, T. Csáki, T. Gaál and A. Kempe, Labelling Multi-tape Automata with Constrained Symbol Classes, Intern. J. of Foundations of Comp. Sc., to appear.
Colloques d’audience internationale avec comité de programme
1. J.-L. Ponty, D. Ziadi and J.-M. Champarnaud, A new quadratic algorithm to convert a regular expression into an automaton, in WIA’96 (Workshop on Implementing Automata), Lecture Notes in Computer Science, D. Raymond and D. Wood eds., Springer-Verlag, 1260(1997), pp. 109—119.
2. J.-M. Champarnaud, D. Ziadi and J.-L. Ponty, Determinization of Glushkov automata, in WIA’98 (Workshop on Implementing Automata), Lecture Notes in Computer Science, J.-M. Champarnaud, D. Maurel and D. Ziadi eds., Springer-Verlag, 1660(1999), pp. 57—68.
3. J.-F. Michon and J.-M. Champarnaud, Automata and Binary Decision Diagrams, in WIA’98 (Workshop on Implementing Automata), Lecture Notes in Computer Science, J.-M. Champarnaud, D. Maurel and D. Ziadi eds., Springer-Verlag, 1660(1999), pp. 178—182.
4. A. Uppman and J.-M. Champarnaud, Autographe : a graphical version of Automate, in WIA’98 (Workshop on Implementing Automata), Lecture Notes in Computer Science, J.-M. Champarnaud, D. Maurel and D. Ziadi eds., Springer-Verlag, 1660(1999), pp. 226—229.
5. P. Andary, P. Caron, J.-M. Champarnaud, G. Duchamp, M. Flouret and E. Laugerotte, SEA: a Symbolic Environment for Automata Theory, in WIA’99 (Workshop on Implementing Automata), Lecture Notes in Computer Science, O. Boldt and H. Jürgensen eds., Springer-Verlag, 2214(2001), pp. 13—26.
6. J.-M. Champarnaud and D. Ziadi, New Finite Automaton Constructions Based on Canonical Derivatives, in CIAA’2000 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, S. Yu and A. Paun eds., Springer-Verlag, 2088(2001), pp. 94—104.
7. J.-M. Champarnaud, Implicit Structures to Implement NFAs from Regular Expressions, in CIAA’2000 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, S. Yu and A. Paun eds., Springer-Verlag, 2088(2001), pp. 80—93.
8. J.-M. Champarnaud and D. Ziadi, Computing the Equation Automaton of a Regular Expression in O(s2) Space and Time, in CPM’2001 (Combinatorial Pattern Matching), Lecture Notes in Computer Science, A. Amir and G. M. Landau eds., Springer-Verlag, 2089(2001), pp. 157—168.
9. J.-M. Champarnaud and G. Duchamp, Brzozowski’s derivatives extended to multiplicities, in CIAA’2001 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, B. W. Watson and D. Wood eds., Springer-Verlag, 2494(2002), pp. 52—64.
10. J.-M. Champarnaud, G. Hansel, T. Paranthoën and D. Ziadi, NFAs Bitstream-Based Random Generation, in DCFS’2002 (Descriptional Complexity of Formal Systems Workshop), Proceedings, J. Dassow, H. Jürgensen and D. Wotschke eds., (2002), pp. 81—94, pdf, ps.
11. J.-M. Champarnaud and F. Coulon, NFA reduction algorithms by means of regular inequalities, in DLT’2003 (Developments in Language Theory), Lecture Notes in Computer Science, Z. Esik and Z. Fülöp eds., Springer-Verlag, 2710(2003), pp. 194—205.
12. J.-M. Champarnaud and T. Paranthoën, Random DFAs over a Non-Unary Alphabet, in DCFS’2003 (Descriptional Complexity of Formal Systems Workshop), Proceedings, E. Csuhaj-Varjú, C. Kintala, D. Wotschke and Gy. Vaszil eds., (2003), pp. 90—101, pdf, ps.
13. J.-M. Champarnaud, E. Laugerotte, F. Ouardi and D. Ziadi, From regular weighted expressions to finite automata, in CIAA’2003 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, O. Ibarra and Z. Dang eds., Springer-Verlag, 2759(2003), pp. 49—60.
14. J.-M. Champarnaud, F. Coulon and T. Paranthoën, Brute Force Determinization of NFAs by Means of State Covers, in CIAA’2004 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, M. Domaratzki, K. Salomaa and S. Yu eds., Springer-Verlag, 3317(2005), pp. 80—89, pdf, ps.
15. J.-M. Champarnaud, F. Nicart and D. Ziadi, Computing the follow automaton of an expression, in CIAA’2004 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, M. Domaratzki, K. Salomaa and S. Yu eds., Springer-Verlag, 3317(2005), pp. 90—101, pdf, ps.
16. J.-M. Champarnaud, F. Guingne and G. Hansel, Reducing cover subsequential transducers, in DCFS’2004 (Descriptional Complexity of Formal Systems Workshop), Proceedings, L. Ilie and D. Wotschke eds., (2004), pp. 131—143.
17. J.-M. Champarnaud, F. Ouardi and D. Ziadi, Follow automaton versus equation automaton, in DCFS’2004 (Descriptional Complexity of Formal Systems Workshop), Proceedings, L. Ilie and D. Wotschke eds., (2004), pp. 145—153, pdf, ps.
18. A. Kempe, J.-M. Champarnaud, J. Eisner, F. Guingne and F. Nicart, A Class of Rational n-WFSM Auto-Intersections, in CIAA’2005 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, J. Farré, I. Litovsky and S. Schmitz eds., Springer-Verlag, 3845(2006), pp. 188—198.
19. A. Kempe, J.-M. Champarnaud, F. Guingne and F. Nicart, WFSM Auto-Intersection and Join Algorithms, in FSMNLP’2005 (Finite-State Methods and Natural Language Processing), Lecture Notes in Computer Science, A. Yli-Jyra ed., Springer, 4002(2006), pp. 120—131.
20. F. Nicart, J.-M. Champarnaud, T. Csáki, T. Gaál and A. Kempe, Multi-tape automata with symbol classes, in CIAA’2006 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, O. Ibarra and Hsu-Chun Yen eds., Springer-Verlag, 4094(2006), pp. 126—136.
21. B. Blanpain, J.-M. Champarnaud, J.-P. Dubernard and D. Geniet, Geometrical Languages, in LATA’2007 (Languages and Automata Theoretical Aspects), Pre-proceedings, Report 35/07, GRLMC Universitat Rovira I Virgili, pp. 127—138.
22. J.-M. Champarnaud, F. Ouardi and D. Ziadi, An efficient computation of the equation K-automaton of a regular K-expression, in DLT’2007 (Developments in Language Theory), Lecture Notes in Computer Science, T. Harju, J. Karhumäki and A. Lepistö eds., Springer-Verlag Berlin Heidelberg, 4588(2007), pp. 145—156.
23. J.-M. Champarnaud, F. Guingne and J. Farré, Reducing Acyclic Cover Transducers, in CIAA’2007 (Conference on Implementing and Applications of Automata), Lecture Notes in Computer Science, Jan Holub and B. Melichar eds., Springer-Verlag, to appear.
Edition d’actes
1. Automata Implementation, proceedings of the Third International Workshop on Implementing Automata (WIA’98, Rouen), Lecture Notes in Computer Science, J.-M. Champarnaud, D. Maurel and D. Ziadi eds., Springer-Verlag, 1660(1999).
2. Automata Implementation, selected papers from the Third International Workshop on Implementing Automata (WIA’98, Rouen), Theoret. Comp. Sc., J.-M. Champarnaud, D. Maurel and D. Ziadi eds., 267(2001).
3. Proceedings of the Fifth Multiconference on Systemics, Cybernetics and Informatics (SCI’2001, Orlando, Florida), N. Callaos, G. Tinetti, J.-M. Champarnaud and J. K. Lee eds., XIV (2001).
4. Automata Implementation, proceedings of the Seventh International Conference on Implementing Automata (CIAA’2002, Tours), Lecture Notes in Computer Science, J.-M. Champarnaud and D. Maurel eds., Springer-Verlag, 2608(2003).
5. Automata Implementation, selected papers from the Seventh International Conference on Implementing Automata (CIAA’2002, Tours), Intern. J. of Foundations of Comp. Sc., J.-M. Champarnaud and D. Maurel eds., 14–6(2003).
Thèses
1. J.-M. Champarnaud, Contribution à l’étude du problème du voyageur de commerce, (1979), Thèse de doctorat, Université de Franche-Comté, sous la direction de M. Tréhel.
2. J.-M. Champarnaud, Outils de calcul pour l’étude des langages rationnels, des automates et des semigroupes finis, (1992), Habilitation à diriger des recherches, Université Paris 7, sous la direction de J.-E. Pin, Rapport LITP 92.13.
Ouvrages
1. J.-M. Champarnaud et G. Hansel, Passeport pour UNIX et C, International Thomson Publishing, (1995), Deuxième édition : Vuibert, 2000.
Autres colloques
1. J.-M. Champarnaud, A programming language for symbolic computation of regular languages, automata and semigroups, in STACS’92 (Symposium on Theoretical Aspects of Computer Science), Lecture Notes in Computer Science, A. Finkel and M. Jantzen eds., Springer-Verlag, 577(1992), pp. 605—606.
2. J.-M. Champarnaud, AUT : un langage pour la manipulation des automates et des semigroupes finis, Actes des Deuxièmes Journées Franco-Belges, D. Krob ed., Publications de l’Université de Rouen, 176(1992), pp. 29—44.
3. J.-M. Champarnaud et D. Ziadi, Expressions rationnelles, dérivées et automates : cas Booléen, in LANFOR’2001 (Groupe de Travail LANgages FORmels de l’AFIT).
4. D. Ziadi et J.-M. Champarnaud, Expressions rationnelles, dérivées et automates : du Booléen aux multiplicités, in LANFOR’2001 (Groupe de Travail LANgages FORmels de l’AFIT).
5. Z. Bennour, J.-M. Champarnaud and D. Ziadi, Supremal Controllable Sublanguage Computation, in SCI’2001 (Systemics, Cybernetics and Informatics), Proceedings, N. Callaos, G. Tinetti, J.-M. Champarnaud and J. K. Lee eds., XIV (2001), pp. 116—120.
6. J.-M. Champarnaud and G. Duchamp, Finite Automata and Boolean Functions, in SCI’2001 (Systemics, Cybernetics and Informatics), Proceedings, N. Callaos, G. Tinetti, J.-M. Champarnaud and J. K. Lee eds., XIV (2001), pp. 126—131, pdf, ps.
7. J.-M. Champarnaud et G. Hansel, Ensembles inévitables et classes de conjugaison, in JM’2002 (Conférence Internationale Journées Montoise d’Informatique Théorique), Actes, V. Berthé ed., (2002).
8. J.-M. Champarnaud, T. Paranthoën et D. Ziadi, Génération aléatoire d’automates non-déterministes par flots de bits équiprobables, in JM’2002 (Conférence Internationale Journées Montoise d’Informatique Théorique), Actes, V. Berthé ed., (2002).
9. J.-M. Champarnaud, A. Khorsi and T. Paranthoën, Split and Join for Minimizing: Brzozowski’s algorithm, in PSC’02 (Prague Stringology Conference), Proceedings, Research report DC–2002–03, M. Balík and M. Simánek eds., Czech Technical University of Prague, (2002), pp. 96—104, pdf, ps.
10. J.-M. Champarnaud, F. Guingne and G. Hansel, Cover K-automata, in WATA’04 (Weighted Automata: Theory and Applications), Proceedings, M. Droste and H. Vogler eds., (2004).
11. J.-M. Champarnaud and F. Coulon, Büchi automata reduction by means of left and right trace inclusion preorders, in JM’2004 (Conférence Internationale Journées Montoise d’Informatique Théorique), Actes, (2004), pdf, ps.
12. A. Kempe, J.-M. Champarnaud and J. Eisner, A note on join and auto-intersection of n-ary rational relations, Proceedings of the Eindhoven FASTAR Days 2004, Research report TU/e CS TR 04—40, 64—78, L. Cleophas and B.W. Watson eds., Eindhoven, the Netherlands, September 2004, pdf, ps.