Christian Choffrut

118 papers A* 6A 6B 5C 8Misc 1Journal 74Unranked 15
YearRankTypeTitle / Venue / Authors
2025 J jnl
Equational theory of ordinals with addition and left multiplication by ω.
Fundam. Informaticae
Christian Choffrut
2025 J jnl
Giovanni in Paris.
Int. J. Found. Comput. Sci.
Christian Choffrut
2024 J jnl
Message complexity for unary multiautomata systems.
CoRR
Christian Choffrut
2024 J jnl
Unary counting quantifiers do not increase the expressive power of Presburger aritmetic: an alternative shorter proof.
CoRR
Christian Choffrut
2023 J jnl
Synchronous orders on the set of integers.
CoRR
Christian Choffrut
2022 J jnl
Decidability of Definability Issues in the Theory of Real Addition.
Fundam. Informaticae
Alexis Bès, Christian Choffrut
2021 J jnl
Theories of real addition with and without a predicate for integers.
Log. Methods Comput. Sci.
Alexis Bès, Christian Choffrut
2020 C conf
$\langle \mathbb {R}, +, <, 1 \rangle $ Is Decidable in $\langle \mathbb {R}, +, < , \mathbb {Z}\rangle $.
LATA
Alexis Bès, Christian Choffrut
2020 J jnl
Theories of real addition with and without a predicate for integers.
CoRR
Alexis Bès, Christian Choffrut
2019 J jnl
Complexity and (Un)decidability of Fragments of 〈 ω ω λ ;× 〉.
Fundam. Informaticae
Alexis Bès, Christian Choffrut
2019 J jnl
Quasi-automatic semigroups.
CoRR
Benjamin Blanchette, Christian Choffrut, Christophe Reutenauer
2019 J jnl
Quasi-automatic semigroups.
Theor. Comput. Sci.
Benjamin Blanchette, Christian Choffrut, Christophe Reutenauer
2018 J jnl
Complexity and (un)decidability of fragments of 〈 ω
CoRR
Alexis Bès, Christian Choffrut
2018 J jnl
Decidability of the existential fragment of some infinitely generated trace monoids: an application to ordinals.
CoRR
Alexis Bès, Christian Choffrut
2018 J jnl
Two equational theories of partial words.
Theor. Comput. Sci.
Christian Choffrut, Zoltán Ésik
2017 J jnl
An Hadamard operation on rational relations.
Theor. Comput. Sci.
Christian Choffrut
2017 J jnl
Sequences of words defined by two-way transducers.
Theor. Comput. Sci.
Christian Choffrut
2016 C conf
Both Ways Rational Functions.
DLT
Christian Choffrut, Bruno Guillon
2015 J jnl
Logical Theory of the Monoid of Languages over a Non Tally Alphabet.
Fundam. Informaticae
Christian Choffrut, Serge Grigorieff
2015 — conf
Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations.
Fields of Logic and Computation II
Christian Choffrut, Serge Grigorieff
2014 — conf
An Algebraic Characterization of Unary Two-Way Transducers.
MFCS (1)
Christian Choffrut, Bruno Guillon
2014 — conf
An algebraic characterization of unary two-way transducers.
ICTCS
Christian Choffrut, Bruno Guillon
2014 J jnl
Deciding Whether or Not a Synchronous Relation is Regular Prefix.
Fundam. Informaticae
Christian Choffrut
2014 J jnl
On the Decidability of the Intersection Problem for Quantum Automata and Context-Free Languages.
Int. J. Found. Comput. Sci.
Alberto Bertoni, Christian Choffrut, Flavio D'Alessandro
2013 C conf
Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem.
Developments in Language Theory
Alberto Bertoni, Christian Choffrut, Flavio D'Alessandro
2013 J jnl
Quantum finite automata and linear context-free languages: a decidable problem
CoRR
Alberto Bertoni, Christian Choffrut, Flavio D'Alessandro
2013 — conf
The Lexicographic Cross-Section of the Plactic Monoid Is Regular.
WORDS
Christian Choffrut, Robert Mercas
2012 J jnl
A Note on the Logical Definability of Rational Trace Languages.
Fundam. Informaticae
Christian Choffrut
2012 J jnl
First-order logics: some characterizations and closure properties.
Acta Informatica
Christian Choffrut, Andreas Malcher, Carlo Mereghetti, Beatrice Palano
2012 J jnl
Rational relations having a rational trace on each finite intersection of rational relations.
Theor. Comput. Sci.
Christian Choffrut, Serge Grigorieff
2011 — conf
On relations of finite words over infinite alphabets.
AFL
Christian Choffrut
2011 J jnl
The Inclusion Problem of Context-Free Languages: Some Tractable Cases.
Int. J. Found. Comput. Sci.
Alberto Bertoni, Christian Choffrut, Roberto Radicioni
2011 J jnl
Unique Decipherability in the Monoid of Languages: An Application of Rational Relations.
Theory Comput. Syst.
Christian Choffrut, Juhani Karhumäki
2010 J jnl
Contextual partial commutations.
Discret. Math. Theor. Comput. Sci.
Christian Choffrut, Robert George Mercas
2010 J jnl
Deciding whether the ordering is necessary in a Presburger formula.
Discret. Math. Theor. Comput. Sci.
Christian Choffrut, Achille Frigeri
2010 J jnl
On Bounded Rational Trace Languages.
Theory Comput. Syst.
Christian Choffrut, Flavio D'Alessandro, Stefano Varricchio
2010 C conf
On the Expressive Power of FO[ + ].
LATA
Christian Choffrut, Andreas Malcher, Carlo Mereghetti, Beatrice Palano
2009 J jnl
Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
Theor. Comput. Sci.
Christian Choffrut, Serge Grigorieff
2009 J jnl
The "equal last letter" predicate for words on infinite alphabets and classes of multitape automata.
Theor. Comput. Sci.
Christian Choffrut, Serge Grigorieff
2009 C conf
The Inclusion Problem of Context-Free Languages: Some Tractable Cases.
Developments in Language Theory
Alberto Bertoni, Christian Choffrut, Roberto Radicioni
2009 Misc conf
Unique Decipherability in the Monoid of Languages: An Application of Rational Relations.
CSR
Christian Choffrut, Juhani Karhumäki
2008 J jnl
Deciding whether a relation defined in Presburger logic can be defined in weaker logics.
RAIRO Theor. Informatics Appl.
Christian Choffrut
2008 — conf
Literal Shuffle of Compressed Words.
IFIP TCS
Alberto Bertoni, Christian Choffrut, Roberto Radicioni
2008 J jnl
Preface.
RAIRO Theor. Informatics Appl.
Christian Choffrut, Loïc Colson
2007 — conf
Definable sets in weak Presburger arithmetic.
ICTCS
Christian Choffrut, Achille Frigeri
2007 J jnl
On the separability of sparse context-free languages and of bounded rational relations.
Theor. Comput. Sci.
Christian Choffrut, Flavio D'Alessandro, Stefano Varricchio
2006 C conf
Context-Free Grammars and XML Languages.
Developments in Language Theory
Alberto Bertoni, Christian Choffrut, Beatrice Palano
2006 J jnl
Decision problems among the main subfamilies of rational relations.
RAIRO Theor. Informatics Appl.
Olivier Carton, Christian Choffrut, Serge Grigorieff
2006 J jnl
Local Limit Properties for Pattern Statistics and Rational Models.
Theory Comput. Syst.
Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati
2006 J jnl
Preface.
RAIRO Theor. Informatics Appl.
Paola Campadelli, Christian Choffrut, Massimiliano Goldwurm, Mauro Torelli
2006 J jnl
Relations over Words and Logic: A Chronology.
Bull. EATCS
Christian Choffrut
2006 J jnl
Separability of rational relations in A* × N
Inf. Process. Lett.
Christian Choffrut, Serge Grigorieff
2005 J jnl
Collage of two-dimensional words.
Theor. Comput. Sci.
Christian Choffrut, Berke Durak
2005 J jnl
Preface.
RAIRO Theor. Informatics Appl.
Christian Choffrut, Yoshiko Wakabayashi
2005 J jnl
Some decision problems on integer matrices.
RAIRO Theor. Informatics Appl.
Christian Choffrut, Juhani Karhumäki
2004 A conf
Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models.
STACS
Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati
2004 C conf
On the Maximum Coefficients of Rational Formal Series in Commuting Variables.
Developments in Language Theory
Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati
2004 — conf
Rational Relations as Rational Series.
Theory Is Forever
Christian Choffrut
2004 J jnl
String-matching with OBDDs.
Theor. Comput. Sci.
Christian Choffrut, Yael Haddad
2003 J jnl
Minimizing subsequential transducers: a survey.
Theor. Comput. Sci.
Christian Choffrut
2003 J jnl
On the number of occurrences of a symbol in words of regular languages.
Theor. Comput. Sci.
Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati
2002 J jnl
Distances between languages and reflexivity of relations.
Theor. Comput. Sci.
Christian Choffrut, Giovanni Pighizzini
2002 J jnl
The commutation of finite sets: a challenging problem.
Theor. Comput. Sci.
Christian Choffrut, Juhani Karhumäki, Nicolas Ollinger
2001 C conf
Elementary Theory of Ordinals with Addition and Left Translation by omega.
Developments in Language Theory
Christian Choffrut
2001 J jnl
Long words: the theory of concatenation and omega-power.
Theor. Comput. Sci.
Stephen L. Bloom, Christian Choffrut
2001 — conf
On Fatou properties of rational languages.
Where Mathematics, Computer Science, Linguistics and Biology Meet
Christian Choffrut, Juhani Karhumäki
2001 J jnl
Periodicity and roots of transfinite strings.
RAIRO Theor. Informatics Appl.
Olivier Carton, Christian Choffrut
2000 — conf
The Theory of Rational Relations on Transfinite Strings.
Words, Languages & Combinatorics
Christian Choffrut, Serge Grigorieff
2000 J jnl
Timed Automata with Periodic Clock Constraints.
J. Autom. Lang. Comb.
Christian Choffrut, Massimiliano Goldwurm
2000 J jnl
Transfinite Equations in Transfinite Strings.
Int. J. Algebra Comput.
Christian Choffrut, Sándor Horváth
1999 J jnl
Decision Issues on Functions Realized by Finite Automata.
J. Autom. Lang. Comb.
Christian Choffrut, Hratchia Pélibossian, Pierre Simonnet
1999 J jnl
Determinants and Möbius functions in trace monoids.
Discret. Math.
Christian Choffrut, Massimiliano Goldwurm
1999 — conf
Uniformization of Rational Relations.
Jewels are Forever
Christian Choffrut, Serge Grigorieff
1998 J jnl
Commutativity in Free Inverse Monoids.
Theor. Comput. Sci.
Christian Choffrut, Flavio D'Alessandro
1998 B conf
Equations in Transfinite Strings.
MFCS
Christian Choffrut, Sándor Horváth
1997 J jnl
A Note on Decidability Questions on Presentations of Word Semigroups.
Theor. Comput. Sci.
Christian Choffrut, Tero Harju, Juhani Karhumäki
1997 — ch.
Combinatorics of Words.
Handbook of Formal Languages (1)
Christian Choffrut, Juhani Karhumäki
1997 — conf
Constructing Sequential Bijections.
Structures in Logic and Computer Science
Christophe Prieur, Christian Choffrut, Michel Latteux
1997 B conf
Distances Between Languages and Reflexivity of Relations.
MFCS
Christian Choffrut, Giovanni Pighizzini
1997 B conf
Generalized Rational Relations and their Logical Definability.
FCT
Christian Choffrut, Leucio Guerra
1995 — ch.
Combinatorics in Trace Monoids I.
The Book of Traces
Christian Choffrut
1995 J jnl
Logical Definability of Some Rational Trace Languages.
Math. Syst. Theory
Christian Choffrut, Leucio Guerra
1995 J jnl
Rational Transductions and Complexity of Counting Problems.
Math. Syst. Theory
Christian Choffrut, Massimiliano Goldwurm
1994 J jnl
Bijective Sequential Mappings of a Free Monoid Onto Another.
RAIRO Theor. Informatics Appl.
Christian Choffrut
1994 J jnl
On Boyer-Moore Automata.
Algorithmica
Ricardo A. Baeza-Yates, Christian Choffrut, Gaston H. Gonnet
1993 J jnl
Conjugacy in Free Inverse Monoids.
Int. J. Algebra Comput.
Christian Choffrut
1993 A conf
On the Logical Definability of Some Rational Trace Languages.
STACS
Christian Choffrut, Leucio Guerra
1993 J jnl
On the Starheight of Some Rational Subsets Closed under Partial Commutations
Inf. Comput.
Christian Choffrut
1992 J jnl
Rational Relations and Ratonal Series.
Theor. Comput. Sci.
Christian Choffrut
1992 B conf
Rational Transductions and Complexity of Counting Problems.
MFCS
Christian Choffrut, Massimiliano Goldwurm
1991 J jnl
Conjugacies.
Bull. EATCS
Christian Choffrut
1991 — conf
Conjugacy in Free Inverse Monoids.
IWWERT
Christian Choffrut
1991 A ed.
STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, February 14-16, 1991, Proceedings
STACS
Christian Choffrut, Matthias Jantzen
1990 J jnl
An Optimal Algorithm for building the Boyer-Moore automaton.
Bull. EATCS
Christian Choffrut
1990 A* conf
Iterated Substitutions and Locally Catanative Systems: A Decidability Result in the Binary Case.
ICALP
Christian Choffrut
1990 A ed.
STACS 90, 7th Annual Symposium on Theoretical Aspects of Computer Science, Rouen, France, February 22-24, 1990, Proceedings
STACS
Christian Choffrut, Thomas Lengauer
1988 — ed.
Automata Networks, LITP Spring School on Theoretical Computer Science, Angelès-Village, France, May 12-16, 1986, Proceedings
Automata Networks
Christian Choffrut
1988 J jnl
Counting with Rational Functions.
Theor. Comput. Sci.
Christian Choffrut, Marcel Paul Schützenberger
1987 A* conf
A Star-Height Problem in Free Monoids with Partial Communications.
ICALP
Christian Choffrut, Christine Duboc
1986 — conf
An Introduction to Automata Network Theory.
Automata Networks
Christian Choffrut
1986 A* conf
Counting with Rational Functions.
ICALP
Christian Choffrut, Marcel Paul Schützenberger
1986 A conf
Décomposition de Fonctions Rationnelles.
STACS
Christian Choffrut, Marcel Paul Schützenberger
1985 J jnl
Test sets for morphisms with bounded delay.
Discret. Appl. Math.
Christian Choffrut, Juhani Karhumäki
1984 A conf
On Extendibility of Unavoidable Sets.
STACS
Christian Choffrut, Karel Culík II
1984 J jnl
On Real-Time Cellular Automata and Trellis Automata.
Acta Informatica
Christian Choffrut, Karel Culík II
1984 J jnl
On extendibility of unavoidable sets.
Discret. Appl. Math.
Christian Choffrut, Karel Culík II
1983 J jnl
Folding of the Plane and the Design of Systolic Arrays.
Inf. Process. Lett.
Christian Choffrut, Karel Culík II
1983 J jnl
Properties of Finite and Pushdown Transducers.
SIAM J. Comput.
Christian Choffrut, Karel Culík II
1983 A* conf
Test Sets for Morphisms with Bounded Delay.
ICALP
Christian Choffrut, Juhani Karhumäki
1981 J jnl
A Closure Property of Deterministic Context-Free Languages.
Inf. Process. Lett.
Christian Choffrut
1981 — conf
Prefix-Preservation fo Rational Partial Functions Is Decidable.
Theoretical Computer Science
Christian Choffrut
1979 A* conf
A Generalization of Ginsburg and Rose's Characterization of G-S-M Mappings.
ICALP
Christian Choffrut
1978 J jnl
Sur les traductions reconnaissables.
RAIRO Theor. Informatics Appl.
Christian Choffrut
1977 J jnl
Applications séquentielles permutables.
J. Inf. Process. Cybern.
Christian Choffrut
1977 J jnl
Sur Certaines Applications Séquentielles Numériques
Inf. Control.
Christian Choffrut
1977 J jnl
Une Caracterisation des Fonctions Sequentielles et des Fonctions Sous-Sequentielles en tant que Relations Rationnelles.
Theor. Comput. Sci.
Christian Choffrut
1976 B conf
Strongly Connected G-S-M Mappings Preserving Conjugation.
MFCS
Christian Choffrut
1972 A* conf
Transducteurs conservant l'imprimitivité du langage d'entrée.
ICALP
Christian Choffrut