# Christian Choffrut

According to our database1, Christian Choffrut authored at least 96 papers between 1972 and 2021.

Collaborative distances:

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2021
Theories of real addition with and without a predicate for integers.
Log. Methods Comput. Sci., 2021

2020
$\langle \mathbb {R}, +, <, 1 \rangle$ Is Decidable in $\langle \mathbb {R}, +, < , \mathbb {Z}\rangle$.
Proceedings of the Language and Automata Theory and Applications, 2020

2019
Quasi-automatic semigroups.
Theor. Comput. Sci., 2019

Complexity and (Un)decidability of Fragments of 〈 ω ω λ ;× 〉.
Fundam. Informaticae, 2019

2018
Two equational theories of partial words.
Theor. Comput. Sci., 2018

Decidability of the existential fragment of some infinitely generated trace monoids: an application to ordinals.
CoRR, 2018

Complexity and (un)decidability of fragments of 〈 ω<sup>ω<sup>λ</sup></sup>; × 〉.
CoRR, 2018

2017
An Hadamard operation on rational relations.
Theor. Comput. Sci., 2017

Sequences of words defined by two-way transducers.
Theor. Comput. Sci., 2017

2016
Both Ways Rational Functions.
Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2015
Logical Theory of the Monoid of Languages over a Non Tally Alphabet.
Fundam. Informaticae, 2015

Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations.
Proceedings of the Fields of Logic and Computation II, 2015

2014
On the Decidability of the Intersection Problem for Quantum Automata and Context-Free Languages.
Int. J. Found. Comput. Sci., 2014

Deciding Whether or Not a Synchronous Relation is Regular Prefix.
Fundam. Informaticae, 2014

An Algebraic Characterization of Unary Two-Way Transducers.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013
Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem.
Proceedings of the Developments in Language Theory - 17th International Conference, 2013

The Lexicographic Cross-Section of the Plactic Monoid Is Regular.
Proceedings of the Combinatorics on Words - 9th International Conference, 2013

2012
Rational relations having a rational trace on each finite intersection of rational relations.
Theor. Comput. Sci., 2012

A Note on the Logical Definability of Rational Trace Languages.
Fundam. Informaticae, 2012

First-order logics: some characterizations and closure properties.
Acta Informatica, 2012

2011
Unique Decipherability in the Monoid of Languages: An Application of Rational Relations.
Theory Comput. Syst., 2011

The Inclusion Problem of Context-Free Languages: Some Tractable Cases.
Int. J. Found. Comput. Sci., 2011

On relations of finite words over infinite alphabets.
Proceedings of the Automata and Formal Languages, 13th International Conference, 2011

2010
On Bounded Rational Trace Languages.
Theory Comput. Syst., 2010

Contextual partial commutations.
Discret. Math. Theor. Comput. Sci., 2010

Deciding whether the ordering is necessary in a Presburger formula.
Discret. Math. Theor. Comput. Sci., 2010

On the Expressive Power of FO[ + ].
Proceedings of the Language and Automata Theory and Applications, 2010

2009
The "equal last letter" predicate for words on infinite alphabets and classes of multitape automata.
Theor. Comput. Sci., 2009

Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
Theor. Comput. Sci., 2009

2008
Preface.
RAIRO Theor. Informatics Appl., 2008

Deciding whether a relation defined in Presburger logic can be defined in weaker logics.
RAIRO Theor. Informatics Appl., 2008

Literal Shuffle of Compressed Words.
Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

2007
On the separability of sparse context-free languages and of bounded rational relations.
Theor. Comput. Sci., 2007

Definable sets in weak Presburger arithmetic.
Proceedings of the Theoretical Computer Science, 10th Italian Conference, 2007

2006
Local Limit Properties for Pattern Statistics and Rational Models.
Theory Comput. Syst., 2006

Decision problems among the main subfamilies of rational relations.
RAIRO Theor. Informatics Appl., 2006

Preface.
RAIRO Theor. Informatics Appl., 2006

Separability of rational relations in A* × N<sup><i>m</i></sup> by recognizable relations is decidable.
Inf. Process. Lett., 2006

Relations over Words and Logic: A Chronology.
Bull. EATCS, 2006

Context-Free Grammars and XML Languages.
Proceedings of the Developments in Language Theory, 10th International Conference, 2006

2005
Collage of two-dimensional words.
Theor. Comput. Sci., 2005

Preface.
RAIRO Theor. Informatics Appl., 2005

Some decision problems on integer matrices.
RAIRO Theor. Informatics Appl., 2005

2004
String-matching with OBDDs.
Theor. Comput. Sci., 2004

Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models.
Proceedings of the STACS 2004, 2004

On the Maximum Coefficients of Rational Formal Series in Commuting Variables.
Proceedings of the Developments in Language Theory, 2004

Rational Relations as Rational Series.
Proceedings of the Theory Is Forever, 2004

2003
Minimizing subsequential transducers: a survey.
Theor. Comput. Sci., 2003

On the number of occurrences of a symbol in words of regular languages.
Theor. Comput. Sci., 2003

2002
Distances between languages and reflexivity of relations.
Theor. Comput. Sci., 2002

The commutation of finite sets: a challenging problem.
Theor. Comput. Sci., 2002

2001
Long words: the theory of concatenation and omega-power.
Theor. Comput. Sci., 2001

Periodicity and roots of transfinite strings.
RAIRO Theor. Informatics Appl., 2001

Elementary Theory of Ordinals with Addition and Left Translation by omega.
Proceedings of the Developments in Language Theory, 5th International Conference, 2001

On Fatou properties of rational languages.
Proceedings of the Where Mathematics, 2001

2000
Timed Automata with Periodic Clock Constraints.
J. Autom. Lang. Comb., 2000

Transfinite Equations in Transfinite Strings.
Int. J. Algebra Comput., 2000

The Theory of Rational Relations on Transfinite Strings.
Proceedings of the International Colloquium on Words, 2000

1999
Decision Issues on Functions Realized by Finite Automata.
J. Autom. Lang. Comb., 1999

Determinants and Möbius functions in trace monoids.
Discret. Math., 1999

Uniformization of Rational Relations.
Proceedings of the Jewels are Forever, 1999

1998
Commutativity in Free Inverse Monoids.
Theor. Comput. Sci., 1998

Equations in Transfinite Strings.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997
Combinatorics of Words.
Proceedings of the Handbook of Formal Languages, Volume 1: Word, Language, Grammar., 1997

A Note on Decidability Questions on Presentations of Word Semigroups.
Theor. Comput. Sci., 1997

Generalized Rational Relations and their Logical Definability.
Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

Constructing Sequential Bijections.
Proceedings of the Structures in Logic and Computer Science, 1997

1995
Rational Transductions and Complexity of Counting Problems.
Math. Syst. Theory, 1995

Logical Definability of Some Rational Trace Languages.
Math. Syst. Theory, 1995

Combinatorics in Trace Monoids I.
Proceedings of the Book of Traces, 1995

1994
Bijective Sequential Mappings of a Free Monoid Onto Another.
RAIRO Theor. Informatics Appl., 1994

On Boyer-Moore Automata.
Algorithmica, 1994

1993
On the Starheight of Some Rational Subsets Closed under Partial Commutations
Inf. Comput., September, 1993

Conjugacy in Free Inverse Monoids.
Int. J. Algebra Comput., 1993

1992
Rational Relations and Ratonal Series.
Theor. Comput. Sci., 1992

1991
Conjugacies.
Bull. EATCS, 1991

1990
An Optimal Algorithm for building the Boyer-Moore automaton.
Bull. EATCS, 1990

Iterated Substitutions and Locally Catanative Systems: A Decidability Result in the Binary Case.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1988
Counting with Rational Functions.
Theor. Comput. Sci., 1988

1987
A Star-Height Problem in Free Monoids with Partial Communications.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

1986
Décomposition de Fonctions Rationnelles.
Proceedings of the STACS 86, 1986

An Introduction to Automata Network Theory.
Proceedings of the Automata Networks, LITP Spring School on Theoretical Computer Science, 1986

1985
Test sets for morphisms with bounded delay.
Discret. Appl. Math., 1985

1984
On extendibility of unavoidable sets.
Discret. Appl. Math., 1984

On Real-Time Cellular Automata and Trellis Automata.
Acta Informatica, 1984

1983
Properties of Finite and Pushdown Transducers.
SIAM J. Comput., 1983

Folding of the Plane and the Design of Systolic Arrays.
Inf. Process. Lett., 1983

1981
A Closure Property of Deterministic Context-Free Languages.
Inf. Process. Lett., 1981

Prefix-Preservation fo Rational Partial Functions Is Decidable.
Proceedings of the Theoretical Computer Science, 1981

1979
A Generalization of Ginsburg and Rose's Characterization of G-S-M Mappings.
Proceedings of the Automata, 1979

1978
RAIRO Theor. Informatics Appl., 1978

1977
Sur Certaines Applications Séquentielles Numériques
Inf. Control., April, 1977

Une Caracterisation des Fonctions Sequentielles et des Fonctions Sous-Sequentielles en tant que Relations Rationnelles.
Theor. Comput. Sci., 1977

Applications séquentielles permutables.
J. Inf. Process. Cybern., 1977

1976
Strongly Connected G-S-M Mappings Preserving Conjugation.
Proceedings of the Mathematical Foundations of Computer Science 1976, 1976

1972
Transducteurs conservant l'imprimitivité du langage d'entrée.
Proceedings of the Automata, 1972