Sylvain Lombardy : recherche

∞

Sylvain Lombardy

Workshop on Symbolic Dynamics and Coding 2007

Publications : Du côté de chez Hal Hal archives Sur la page du laboratoire On the Labs page

Automate universel, hauteur d'étoile, langages réversibles

Universal automaton, star height, reversible languages

On the star height of rational languages. A new proof for two old results. ( Jacques Sakarovitch)

- ENST 2001, (Postscript, pdf)
- Proc. of 3rd Int. Conf. on Languages, Words and Combinatorics, Kyoto 00 (M. Ito, ed.), (World Scientific, 2003) 266-285. (Postscript,pdf)
- bibtex

@incollection {LombSaka03SH,
    AUTHOR = {Lombardy, Sylvain and Sakarovitch, Jacques},
     TITLE = {On the star height of rational languages: a new presentation
              for two old results},
 BOOKTITLE = {Words, languages \& combinatorics, III (Kyoto, 2000)},
     PAGES = {266--285},
 PUBLISHER = {World Sci. Publishing},
      YEAR = {2003},
   MRCLASS = {68Q45}
}

Star height of reversible languages and universal automata. ( Jacques Sakarovitch)

- Latin 2002 ()
- Latin 2002, Lect. Notes in Comp. Sci., 2286 (Springer, 2002), 76-89. (Postscript, pdf)
- bibtex

@inproceedings{LombSaka02SH,
    AUTHOR = {Lombardy, Sylvain and Sakarovitch, Jacques},
     TITLE = {Star height of reversible languages and universal automata},
     PAGES = {76--90},
  CROSSREF = {latin2002}
}

@proceedings{latin2002,
    EDITOR = {Rajsbaum, Sergio},
     TITLE = {LATIN 2002: Theoretical Informatics, 5th Latin American
              Symposium, Cancun, Mexico, April 3-6, 2002, Proceedings},
 BOOKTITLE = {LATIN 2002},
 PUBLISHER = {Springer},
    SERIES = {Lecture Notes in Computer Science},
    VOLUME = {2286},
      YEAR = {2002},
      ISBN = {3-540-43400-3},
      ISSN = {0302-9743}
}

On the construction of reversible automata for reversible languages.

- ICALP'02 ()
- ICALP 2002, Lect. Notes in Comp. Sci., 2380 (Springer, 2002), 170-182. (Postscript, pdf)
- bibtex

@inproceedings{Lomb02Re,
    AUTHOR = {Lombardy, Sylvain},
     TITLE = {On the construction of reversible automata for reversible languages},
     PAGES = {170--182},
  CROSSREF = {icalp2002}
}

@proceedings{icalp2005,
     TITLE = {Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005,
              Lisbon, Portugal, July 2005, Proceedings},
 BOOKTITLE = {ICALP 2005},
    EDITOR = {Caires, Lu\'{\i}s and
              F. Italiano, Giuseppe and
              Monteiro, Lu\'{\i}s and
              Palamidessi, Catuscia and
              Yung, Moti},
 PUBLISHER = {Springer},
    SERIES = {Lecture Notes in Computer Science},
    VOLUME = {3580},
      YEAR = {2005},
      ISBN = {3-540-27580-0}}

On the size of the universal automaton of a regular language.

- STACS'07
- STACS 2007, Lect. Notes in Comp. Sci., 4393 (Springer, 2007), 85-96.
- bibtex

@inproceedings{Lomb07,
    AUTHOR = {Lombardy, Sylvain},
     TITLE = {On the size of the Universal Automaton of a Regular Language},
     PAGES = {85-96},
  CROSSREF = {stacs2007}
}

@proceedings{stacs2007,
    EDITOR = {Thomas, Wolfgang and
              Weil, Pascal},
     TITLE = {24th Annual Symposium on Theoretical Aspects of Computer Science,
              STACS 2007, Aachen, Germany, February 22-24, 2007, Procedings},
 BOOKTITLE = {STACS 2007},
 PUBLISHER = {Springer},
    SERIES = {Lecture Notes in Computer Science},
    VOLUME = {4393},
      YEAR = {2007},
      ISBN = {3-540-70917-7}
}

The universal automaton. ( Jacques Sakarovitch)

- Logic and Automata, Texts in Logic and Games, 2 (Amsterdam University Press, 2008), 457-504.
- bibtex

@incollection{LombSaka07,
    AUTHOR = {Lombardy, Sylvain and Sakarovitch, Jacques},
     TITLE = {The universal automaton},
     PAGES = {457-504},
  CROSSREF = {LogAndAut08}
}

@book{LogAndAut08,
    EDITOR = {Flum, J{\"o}rg and
              Gr{\"a}del, Erich and
              Wilke, Thomas},
     TITLE = {Logic and Automata - History and Perspectives},
 BOOKTITLE = {Logic and Automata},
 PUBLISHER = {Amsterdam University Press},
    SERIES = {Texts in Logic and Games},
    VOLUME = {2},
      YEAR = {2008},
      ISBN = {978-90-5356-576-6}
}

Expressions rationnelles, reconstruction d'automates

Rational expressions, conversion into automata

Derivatives of rational expressions with multiplicity. ( Jacques Sakarovitch)

- ENST, 2001 (Postscript, pdf)
- MFCS 2002, Lect. Notes in Comp. Sci., 2420 (Springer, 2002), 471-482.
- TCS 332 (Elsevier, 2005), 141-177. (Postscript)
- bibtex

@article{LombSaka05Dr,
    AUTHOR = {Lombardy, Sylvain and
               Sakarovitch, Jacques},
     TITLE = {Derivatives of rational expressions with multiplicity},
   JOURNAL = {Theoretical Computer Science},
 PUBLISHER = {Elsevier},
    VOLUME = {332},
      YEAR = {2005},
     PAGES = {141--177}
}

How expressions can code for automata. ( Jacques Sakarovitch)

- Latin 2004
- Latin 2004, Lect. Notes in Comp. Sci., 2976 (Springer, 2004), 242-251.
- : ITA 39.1 (EDP Sciences, 2005), 217-237. (Postscript)
- bibtex

@article{LombSaka05CA,
    AUTHOR = {Lombardy, Sylvain and
               Sakarovitch, Jacques},
     TITLE = {How expressions can code for automata},
   JOURNAL = {RAIRO - Theoretical Informatics and Applications},
 PUBLISHER = {EDP Sciences},
    VOLUME = {39},
      YEAR = {2005},
     PAGES = {217--237}
}

On the number of broken derived terms of a rational expression. ( Jacques Sakarovitch Pierre-Yves Angrand)

Automates Max-plus, séquentialisation

Max-plus automata, sequentialization

Sequentialization and unambiguity of (max,+) rational series over one letter.

- Satellite Workshop on Max-Plus Algebras, IFAC SSSC'01, Prague, Elsevier. (Postscript, pdf)
- bibtex

@InProceedings{Lomb01MP,
    AUTHOR = {Lombardy, Sylvain},
     TITLE = {Sequentialization and unambiguity of (max,+) rational series over one letter},
 BOOKTITLE = {Workshop on max-plus algebras and Their Applications to Discrete-event Systems, Theoretical Computer Science, and Optimization},
    EDITOR = {Gaubert, St\'ephane and Loiseau, Jean-Jacques}, 
   ADDRESS = {Prague},
 PUBLISHER = {IFAC, Elsevier Sciences},
      YEAR = {2001}
}

Deciding the sequentiality of a finitely ambiguous Max-Plus automaton.
( Ines Klimann, Jean Mairesse Christophe Prieur)

Deciding unambiguity and sequentiality from a finitely ambiguous Max-Plus automaton.
( Ines Klimann, Jean Mairesse Christophe Prieur)

Version finale du précédent Final version of the previous one - LIAFA
- : TCS 327(3) (Elsevier, 2004), 349-373.
- HAL
- bibtex

@article{KLMP04MP,
    AUTHOR = {Klimann, Ines and Lombardy, Sylvain and Mairesse, Jean and Prieur, Christophe},
     TITLE = {Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton},
   JOURNAL = {Theoretical Computer Science},
 PUBLISHER = {Elsevier},
    VOLUME = {327},
      YEAR = {2004},
    NUMBER = {3},
     PAGES = {349--373},
        EE = {http://dx.doi.org/10.1016/j.tcs.2004.02.049}}

Series which are both max-plus and min-plus rational are unambiguous. ( Jean Mairesse)

- WATA 2004
- LIAFA
- : ITA 40 (EDP sciences, 2006), 1-14.
- HAL
- bibtex

@article{LombMair06MP,
    AUTHOR = {Lombardy, Sylvain and Mairesse, Jean},
     TITLE = {Series which are both max-plus and min-plus rational are unambiguous},
   JOURNAL = {RAIRO - Theoretical Informatics and Applications},
 PUBLISHER = {EDP Sciences},
     PAGES = {1--14},
      YEAR = {2006},
        EE = {http://dx.doi.org/10.1051/ita:2005042}
}

Sequential ? ( Jacques Sakarovitch)

- Survey : TCS 356(1-2) (Elsevier, 2006), 224-244.
- bibtex

@article{LombSaka06Se,
    AUTHOR = {Lombardy, Sylvain and Sakarovitch, Jacques},
     TITLE = {Sequential ?},
   JOURNAL = {Theoretical Computer Science},
 PUBLISHER = {Elsevier},
    VOLUME = {359},
      YEAR = {2006},
    NUMBER = {1-2},
     PAGES = {224--244},
        EE = {http://dx.doi.org/10.1016/j.tcs.2006.01.028}
}

Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata ( Daniel Kirsten)

- STACS 2009, Proceedings.
- HAL
- bibtex

@inproceedings{KirsLomb09,
    AUTHOR = {Kirsten, Daniel and Lombardy, Sylvain},
     TITLE = {Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata},
     PAGES = {589--600},
  CROSSREF = {stacs2009}
       URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1850},
        EE = {http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-18509}
}

@proceedings{stacs2009,
    EDITOR = {Albers, Susanne and Marion, Jean-Yves},
     TITLE = {26th Annual Symposium on Theoretical Aspects of Computer Science,
              STACS 2009, Freiburg, Germany, February 26-29, 2009, Procedings},
 BOOKTITLE = {STACS 2009},
 PUBLISHER = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  ADDRESS  = {Dagstuhl, Germany},
      YEAR = {2009}
}

Radix cross-sections for length morphisms ( Jacques Sakarovitch) - WORDS 2009

Vaucanson

Introducing Vaucanson. ( Raphaël Poss, Yann Régis-Gianas Jacques Sakarovitch)

- CIAA 2003, Lect. Notes in Comp. Sci., 2759 (Springer, 2003), 96-107.
- : TCS 328 (Elsevier, 2004), 77-96.
- bibtex

@article{LRS04Va,
    AUTHOR = {Lombardy, Sylvain and
               R{\'e}gis-Gianas, Yann and
               Sakarovitch, Jacques},
     TITLE = {Introducing {\sc Vaucanson}},
   JOURNAL = {Theoretical Computer Science},
 PUBLISHER = {Elsevier},
    VOLUME = {328},
      YEAR = {2004},
    NUMBER = {1-2},
     PAGES = {77--96},
        EE = {http://dx.doi.org/10.1016/j.tcs.2004.07.007}
}

Inside Vaucanson. ( Thomas Claveirole, Sarah O'Connor, Louis-Noël Pouchet Jacques Sakarovitch)

- CIAA 2005, Lect. Notes in Comp. Sci., 3845 (Springer, 2006), 116-128.
- bibtex

@inproceedings{CLOPS05Va,
    AUTHOR = {Claveirole, Thomas and
              Lombardy, Sylvain and
              O'Connor, Sarah and
              Pouchet, Louis-No{\"e}l and
              Sakarovitch, Jacques},
     TITLE = {Inside {\sc Vaucanson}},
        EE = {http://dx.doi.org/10.1007/11605157_10},
  CROSSREF = {ciaa2005}
 }

@proceedings{ciaa2005,
    EDITOR = {Farr{\'e}, Jacques and
              Litovsky, Igor and
              Schmitz, Sylvain},
 BOOKTITLE = {CIAA 2005},
 PUBLISHER = {Springer},
    SERIES = {Lecture Notes in Computer Science},
      YEAR = {2005},
    VOLUME = {3845},
      ISBN = {3-540-31023-1}
}

Automates à multiplicité

Weighted automata

On the equivalence of Z-automata ( Marie-Pierre Béal Jacques Sakarovitch)

- ICALP 2005, Lect. Notes in Comp. Sci., 3580 (Springer, 2005), 397-409.
- bibtex

@inproceedings{BLS05Cj,
    AUTHOR = {B{\'e}al, Marie-Pierre and
              Lombardy, Sylvain and
              Sakarovitch, Jacques},
     TITLE = {On the equivalence of $\mathbb{Z}$-automata},
     PAGES = {397--409},
        EE = {http://dx.doi.org/10.1007/11523468_33},
  CROSSREF = {icalp2005}
 }

@proceedings{icalp2005,
 BOOKTITLE = {ICALP 2005},
    EDITOR = {Caires, Lu\'{\i}s and
              F. Italiano, Giuseppe and
              Monteiro, Lu\'{\i}s and
              Palamidessi, Catuscia and
              Yung, Moti},
 PUBLISHER = {Springer},
    SERIES = {Lecture Notes in Computer Science},
    VOLUME = {3580},
      YEAR = {2005},
      ISBN = {3-540-27580-0}}

Conjugacy and equivalence of weighted automata and functional transducers
( Marie-Pierre Béal Jacques Sakarovitch)

-
- CSR 2006, Lect. Notes in Comp. Sci., 3967 (Springer, 2006), 58-69.
- bibtex

@inproceedings{BLS06Cj,
    AUTHOR = {B{\'e}al, Marie-Pierre and
              Lombardy, Sylvain and
              Sakarovitch, Jacques},
     TITLE = {Conjugacy and Equivalence of Weighted Automata and Functional Transducers},
     PAGES = {58-69},
        EE = {http://dx.doi.org/10.1007/11753728_9},
  CROSSREF = {csr2006}
}

@proceedings{csr2006,
    EDITOR = {Grigoriev, Dima and
              Harrison, John and
              Hirsch, Edward A.},
     TITLE = {Computer Science - Theory and Applications, First International
              Computer Science Symposium in Russia, CSR 2006, St. Petersburg,
              Russia, June 8-12, 2006, Proceedings},
 BOOKTITLE = {CSR 2006},
 PUBLISHER = {Springer},
    SERIES = {Lecture Notes in Computer Science},
    VOLUME = {3967},
      YEAR = {2006},
      ISBN = {3-540-34166-8}
}