Christian Choffrut

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

Collaborative distances:



In proceedings 
PhD thesis 




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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RAIRO Theor. Informatics Appl., 2005

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

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

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

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

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

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

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

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

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

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

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

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

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

On Boyer-Moore Automata.
Algorithmica, 1994

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

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

Bull. EATCS, 1991

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

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

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

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

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

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

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

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

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

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

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

Sur les traductions reconnaissables.
RAIRO Theor. Informatics Appl., 1978

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

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

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