Christian Choffrut

According to our database1, Christian Choffrut authored at least 102 papers between 1972 and 2018.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

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 〈 ωωλ; × 〉.
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. Inform., 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. Inform., 2014

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

An algebraic characterization of unary two-way transducers.
Proceedings of the 15th Italian Conference on Theoretical Computer Science, 2014

2013
Quantum finite automata and linear context-free languages: a decidable problem
CoRR, 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. Inform., 2012

First-order logics: some characterizations and closure properties.
Acta Inf., 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.
Discrete Mathematics & Theoretical Computer Science, 2010

Deciding whether the ordering is necessary in a Presburger formula.
Discrete Mathematics & Theoretical Computer Science, 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

The Inclusion Problem of Context-Free Languages: Some Tractable Cases.
Proceedings of the Developments in Language Theory, 13th International Conference, 2009

Unique Decipherability in the Monoid of Languages: An Application of Rational Relations.
Proceedings of the Computer Science, 2009

2008
Preface.
ITA, 2008

Deciding whether a relation defined in Presburger logic can be defined in weaker logics.
ITA, 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.
ITA, 2006

Preface.
ITA, 2006

Separability of rational relations in A* × Nm by recognizable relations is decidable.
Inf. Process. Lett., 2006

Relations over Words and Logic: A Chronology.
Bulletin of the 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.
ITA, 2005

Some decision problems on integer matrices.
ITA, 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.
ITA, 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.
Journal of Automata, Languages and Combinatorics, 2000

Transfinite Equations in Transfinite Strings.
IJAC, 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.
Journal of Automata, Languages and Combinatorics, 1999

Determinants and Möbius functions in trace monoids.
Discrete Mathematics, 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.
Handbook of Formal Languages (1), 1997

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

Distances Between Languages and Reflexivity of Relations.
Proceedings of the Mathematical Foundations of Computer Science 1997, 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.
Mathematical Systems Theory, 1995

Logical Definability of Some Rational Trace Languages.
Mathematical Systems Theory, 1995

1994
Bijective Sequential Mappings of a Free Monoid Onto Another.
ITA, 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.
IJAC, 1993

On the Logical Definability of Some Rational Trace Languages.
Proceedings of the STACS 93, 1993

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

Rational Transductions and Complexity of Counting Problems.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

1991
Conjugacies.
Bulletin of the EATCS, 1991

Conjugacy in Free Inverse Monoids.
Proceedings of the Word Equations and Related Topics, Second International Workshop, 1991

1990
An Optimal Algorithm for building the Boyer-Moore automaton.
Bulletin of the 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

Counting with Rational Functions.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985
Test sets for morphisms with bounded delay.
Discrete Applied Mathematics, 1985

1984
On extendibility of unavoidable sets.
Discrete Applied Mathematics, 1984

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

On Extendibility of Unavoidable Sets.
Proceedings of the STACS 84, 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

Test Sets for Morphisms with Bounded Delay.
Proceedings of the Automata, 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
Sur les traductions reconnaissables.
ITA, 1978

1977
Sur Certaines Applications Séquentielles Numériques
Information and 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.
Elektronische Informationsverarbeitung und Kybernetik, 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.
ICALP, 1972


  Loading...