C. Choffrut,
"An Hadamard operation on rational relations ",
Theorerical Computer Science
[pdf]
To appear.
C. Choffrut,
S. Holub,
"A presentation of a finitely generated submonoid
of invertible endomorphisms of the free monoid ",
Semigroup Forum
[pdf]
To appear.
C. Choffrut,
S. Grigorieff,
"
Logical Theory of the Monoid of Languages over a Non Tally Alphabet
",
Fundam. Inform.
vol. 138, issues 1-2 , 2015, p. 159-177.
[pdf]
C. Choffrut,
S. Grigorieff,
"Monadi$c Theory of a Linear Order Versus the Theory of its
Subsets with the Lifted Min/Max Operations"
Fields of Logic and Computation II,
Lecture Notes in Computer Science 9300:109--128, 2015.
[pdf]
C. Choffrut,
S. Grigorieff,
Logical theory of the additive monoid of subsets of natural integers
Automata, universality, computation.
Tribute to
Maurice Margenstern,
editor:
Andrew Adamatsky,
39--74, 2015.[pdf]
C. Choffrut,
Alberto Bertoni,
and Flavio d'Alessandro,
"
On the Decidability of the Intersection Problem for Quantum Automata
and Context-Free Languages ",
Journal version of DLT 2013,
Int. J. Found. Comput. Sci. , vol. 25, number 8, 2014, p. 1065-1082
C. Choffrut,
"
Deciding Whether or Not a Synchronous Relation is Regular Prefix ",
Fundam. Inform. , vol. 132, number 4, 2014, p. 439-459.
C. Choffrut,
S. Grigorieff,
"
Rational relations having a rational trace on each finite intersection of rational relations
Theoretical Computer Science,, 454:88--94, 2012.
[pdf]
C. Choffrut,
A. Malcher ,
C. Mereghetti ,
B. Palano
",
First-order logics: some characterizations and closure properties ",
Journal version of LATA 2011
Acta Inf. , vol. 49, number 4, 2012, p. 225-248.
C. Choffrut,
A Note on the Logical Definability of Rational Trace Languages,
Fundam. Inform.
,
vol. 116, 1-4, 2012, p.45-50.
C. Choffrut,
Juhani Karhumäki,
" Unique decipherability
in the monoid of languages: an application of rational
relations ",
Journal version of CSR 2009,
Theory Comput. Syst., vol. 49, 2011, p. 355-364.
C. Choffrut,
A. Malcher ,
C. Mereghetti ,
B. Palano ,
"
On the Expressive Power of FO[ + ], ",
LATA Conference Theory of Computing Systems, LNCS 6031, 2010, p. 190-201.
C. Choffrut,
F. D'Alessandro ,
S. Varricchio ,
"
On bounded rational trace languages, ",
Theory of Computing Systems, vol. 46, 2, 2010, p. 351-369.
C. Choffrut,
Achille Frigeri,
Deciding whether the ordering is necessary in a Presburger formula,
Discrete Mathematics and Theoretical Computer Science ,
vol. 12, 1, 2010, p. 21-38.
C. Choffrut,
Robert Mercas ,
Contextual partial commutations,
Discrete Mathematics and Theoretical Computer Science
,
vol. 12, 4, 2010, p. 59-72.
C. Choffrut,
Juhani Karhumäki,,
Unique decipherability
in the monoid of languages: an application of rational
relations ",
CSR Conference, Springer Verlag, LNCS 5675, 2009, p. 71-79.
C. Choffrut,
A. Bertoni, et
R. Radicioni,
"
The Inclusion Problem of Context-Free Languages: Some Tractable Cases "
Developments in Language Theory,
LNCS 5583, 2009, p. 103-112.
C. Choffrut,
S. Grigorieff,
"
The "equal last letter" predicate for words on
infinite alphabets and classes of multitape automata ",
Theoretical Computer Science,
vol. 410, issues 30-32, 2009, p. 2870-2884.
C. Choffrut,
S. Grigorieff,
"
Finite $n$-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. ",
Theoretical Computer Science, vol. 410, issues 1, 2009, p. 16-34.
C. Choffrut,
"
Deciding whether a relation defined in Presburger
logic can be defined in weaker logics ",
Theoretical Informatics and Applications,
Vol. 42, 1, 2008, p.121-136.
C. Choffrut,
S. Grigorieff,
"
The decision problem for some logics for finite words
on infinite alphabets ",
Notes of scientific seminars of POMI, 2008
(Special volume dedicated to Yuri Matiyasevich's 60th birthday).
C. Choffrut et A.Frigeri,
"
Definable sets in the weak Presburger arithmetic
",
Italian Conference on Theoretical Computer Science,
Rom, 3--5 October 2007.
C. Choffrut,
F. D'Alessandro ,
S. Varricchio ,
"
On the separability of sparse context-free languages
and of bounded rational relations ",
Theoret. Comput. Sci., available on line 7 April 2007
C. Choffrut, Y. Haddad,
"
Recognizing group languages with OBDDs ",
Vietnam Journal of Mathematics, Vol.34, Number 4, pp. 269--279, 2006
C. Choffrut,
Paola Campadelli et
Massimiliano Goldwurm ,
Edition du volume 40(2) de la RAIRO/ITA , 2006
C. Choffrut,
Alberto Bertoni et
Beatrice Palano ,
Context-Free Grammars and XML Languages,
Developments in Language Theory,
pp. 108-119, 2006
C. Choffrut,
"
Relations over words and logic: a chronology
",
Bulletin of the EATCS, numéro 89, June 2006, pp. 159-163.
C. Choffrut,
S. Grigorieff,
"
Separability of rational subsets
by recognizable subsets is decidable in A*xN^m ",
Information Processing Letters,
Volume 99(1), pp. 27-32, 2006
O. Carton, C. Choffrut,
S. Grigorieff,
"
Decision problems among the main subfamilies of rational relations ",
RAIRO/ITA, volume 40, pp. 255-275, 2006
A. Bertoni, C. Choffrut,
M. Goldwurm ,
V. Lonati ,
Local Limit Properties for Pattern Statistics and Rational Models,
Theory Comput. Syst., Volume 39(1), pp. 209-235, 2006
C. Choffrut,
B. Durak,
"
Collage of two-dimensional words ",
Theoret. Comput. Sci., 340(1), pp. 364-380, 2005
C. Choffrut,
Juhani Karhumäki,
"
Some decision problems on integer matrices ",
RAIRO/ITA, Vol. 39(1), pp. 125-132, 2005
C. Choffrut,
M. Goldwurm , V. Lonati ,
"
On the maximum coefficients of rational formal
series in commuting variables ",
Communication à
DLT'04 ,
8th Int. Conf. on Developments in
Language Theory, LNCS 3340, pp. 114-126, 2004
C. Choffrut, Y. Haddad,
"
String-matching with OBDDs",
Theoretical Computer Science, Volume 313(2-3),
pp. 187-198, 2004
C. Choffrut,
"
Rational relations as rational series",
Theory is forever,
Essays dedicated to Arto Salomaa on the Occasion
of His 70th Birthday,Juhani Karhumäki,
Hermann Maurer and Gheorghe Paun (Editors), LNCS 3113, pp. 29--34, 2004
A. Bertoni, C. Choffrut,
M. Goldwurm , V. Lonati ,
"
On the number of occurrences of a symbol in words of regular
languages ",
Theoretical Computer Science, Volume 302(1-3),
pp. 431-456, 2003
Christian Choffrut,
"
Minimizing subsequential transducers: a survey ",
Theoret.Comput. Sci, 292, 1, 2003, pp. 131-143.
C. Choffrut,
"
A short introduction to automatic group theory ",
in Semigroups, Algorithms, Automata
and Languages, Gracinda M.S. Gomes, Jean-Éric Pin, Pedro V.
Silva (Editors),
World Scientific, 2002.
C. Choffrut,
"
Elementary Theory of Ordinals with Addition and Left Translation by omega",
DLT 2001, Werner Kuich, Grzegorz Rozenberg and Arto Salomaa (Editors),
LNCS 2295, 2002, pp. 15-20.
A. Bertoni, C. Choffrut,
M. Goldwurm , V. Lonati ,
"
The symbol-periodicity of irreducible finite automata ",
Words 2001, Palermo (rapport interne de l'Université de Milan,
Italie.
Christian Choffrut,
Olivier Carton ,
"
Periodicity and roots of transfinite strings,
",
RAIRO/ITA. 2001, 35, 6, pp.525-534.
Stephen Bloom , Christian Choffrut, [ps.gz, 67ko] "
Long Words, the theory of concatenation and omega power,
",
Theoret. Comput. Sci., 259 , 2001,
pp. 533-548
Christian Choffrut,
Giovanni Pighizzini ,
"
Distances between languages and reflexivity of relations ",
Theoret. Comput. Sci., 286 , Vol. 1, 2001, pp. 117-138.
aussi dans
Proceedings MFCS'97, Lecture Notes in Computer Science # 1295,
1997, pp. 199-208.
Christian Choffrut,
"
Matrix representations of trace monoids
"
Contribution au colloque sur
les traces organisé à Milan,
juin 2000 par
M. Goldwurm
Christian Choffrut,
Sándor Horváth,
"
Transfinite equations in transfinite strings
"
International Journal
of Algebra and Computation, 10, 2000, 625-649
Christian Choffrut,
Juhani Karhumäki , [ps.gz, 43ko] "
On Fatou properties of rational languages
"
in C. Martin-Vide and V. Mitrana (eds), Where
Mathematics, Computer Science, Linguistics and Biology Meet,
Kluwer, Dordrecht, 2000, pp. 227-235
Christian Choffrut,
Juhani Karhumäki,
Nicolas Ollinger,
"
The commutation of finite sets:
a challenging problem
"
édition spéciale
de Theoret. Comput. Sci. de la conférence
"Words "
Christian Choffrut ,
M. Goldwurm ,
" Timed automata with periodic
clock constraints ",
Journal of Automata, Languages and Combinatorics,
5, pp. 371-404, 2000
Christian Choffrut,
S. Grigorieff
Uniformization
of rational relations ,
Jewels are forever, Springer Verlag, 1999
Christian Choffrut,
Hratcha Pelibossian, Pierre Simonnet, "
Decision issues on functions realized
by finite automata
Journal of Automata, Languages and Combinatorics, 4, 1999, 3, pp. 171-181
Christian Choffrut,
M. Goldwurm ,
Déterminants et fonction de Möbius
Discrete Mathematics, 194, 1999, pp. 239 - 247
Christian Choffrut,
F. D'Alessandro ,
Commutativity
in Free Inverse Monoids,
Theoret. Comput. Sci. , 259 , 1998
pp. 35--54
Christian Choffrut, Leucio Guerra,
Generalized Rational Relations and their Logical Definability,
FCT, Lecture Notes in Computer Science, Springer Verlag,
1279 , 1997, pp. 138--149.
Christian Choffrut,
Juhani Karhumäki ,
"
Combinatorics of Words ",
Handbook of Formal Languages,
Springer Verlag,1997.
Christian Choffrut,
Tero Harju et
Juhani Karhumäki ,
A note on decidability questions on presentations of word semigroups,
Theoret. Comput. Sci. , 183, 1997, pp. 83--92.
Christophe Prieur, Christian Choffrut, Michel Latteux,
" Constructing sequential bijections ",
Lecture Notes in Computer Science, # 1262, J. Mycielski, G. Rozenberg and A. Salomaa Ed., 1995, pp. 308--322.
Christian Choffrut ,
M. Goldwurm ,
Rational Transductions and Complexity of Counting Problems,
Math. Sci. Theory, 28,
, 1995, pp. 437--450.
Christian Choffrut, Leucio Guerra,
Logical Definability of Some Rational Trace Languages,
Math. Sci. Theory, 28,
, 1995, pp. 397--420.
Christian Choffrut, "
Equations in Trace Monoids, The Book of Traces,
"
World Scientific, G. Rozenberg, A. Salomaa Ed., 1995.
Ricardo Baeza-Yates , Christian Choffrut and Gaston Gonnet,
"
On Boyer-Moore Automata, "
1994,
Algorithmica, 12 ,
pp. 268--292