Christian Choffrut

CoRR, 2023

2022

Decidability of Definability Issues in the Theory of Real Addition.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2022

2021

Theories of real addition with and without a predicate for integers.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2021

2020

$\langle \mathbb {R}, +, <, 1 \rangle $ Is Decidable in $\langle \mathbb {R}, +, < , \mathbb {Z}\rangle $.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2020

2019

Quasi-automatic semigroups.

[BibT_eX]

[DOI]

Benjamin Blanchette

Christophe Reutenauer

Theor. Comput. Sci., 2019

Complexity and (Un)decidability of Fragments of 〈 ω ω λ ;× 〉.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2019

2018

Two equational theories of partial words.

[BibT_eX]

[DOI]

Zoltán Ésik

Theor. Comput. Sci., 2018

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

[BibT_eX]

[DOI]

CoRR, 2018

Complexity and (un)decidability of fragments of 〈 ωωλ; × 〉.

[BibT_eX]

[DOI]

CoRR, 2018

2017

An Hadamard operation on rational relations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Sequences of words defined by two-way transducers.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

2016

Both Ways Rational Functions.

[BibT_eX]

[DOI]

Bruno Guillon

Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2015

Logical Theory of the Monoid of Languages over a Non Tally Alphabet.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2015

Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2014

Deciding Whether or Not a Synchronous Relation is Regular Prefix.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2014

An Algebraic Characterization of Unary Two-Way Transducers.

[BibT_eX]

[DOI]

Bruno Guillon

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 17th International Conference, 2013

The Lexicographic Cross-Section of the Plactic Monoid Is Regular.

[BibT_eX]

[DOI]

Robert Mercas

Proceedings of the Combinatorics on Words - 9th International Conference, 2013

2012

Rational relations having a rational trace on each finite intersection of rational relations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

A Note on the Logical Definability of Rational Trace Languages.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2012

First-order logics: some characterizations and closure properties.

[BibT_eX]

[DOI]

Acta Informatica, 2012

2011

Unique Decipherability in the Monoid of Languages: An Application of Rational Relations.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

The Inclusion Problem of Context-Free Languages: Some Tractable Cases.

[BibT_eX]

[DOI]

Roberto Radicioni

Int. J. Found. Comput. Sci., 2011

On relations of finite words over infinite alphabets.

[BibT_eX]

Proceedings of the Automata and Formal Languages, 13th International Conference, 2011

2010

On Bounded Rational Trace Languages.

[BibT_eX]

[DOI]

Stefano Varricchio

Theory Comput. Syst., 2010

Contextual partial commutations.

[BibT_eX]

[DOI]

Robert George Mercas

Discret. Math. Theor. Comput. Sci., 2010

Deciding whether the ordering is necessary in a Presburger formula.

[BibT_eX]

[DOI]

Achille Frigeri

Discret. Math. Theor. Comput. Sci., 2010

On the Expressive Power of FO[ + ].

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

2008

Preface.

[BibT_eX]

[DOI]

Loïc Colson

RAIRO Theor. Informatics Appl., 2008

Deciding whether a relation defined in Presburger logic can be defined in weaker logics.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2008

Literal Shuffle of Compressed Words.

[BibT_eX]

[DOI]

Roberto Radicioni

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.

[BibT_eX]

[DOI]

Stefano Varricchio

Theor. Comput. Sci., 2007

Definable sets in weak Presburger arithmetic.

[BibT_eX]

Achille Frigeri

Proceedings of the Theoretical Computer Science, 10th Italian Conference, 2007

2006

Local Limit Properties for Pattern Statistics and Rational Models.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2006

Decision problems among the main subfamilies of rational relations.

[BibT_eX]

[DOI]

Olivier Carton

RAIRO Theor. Informatics Appl., 2006

Preface.

[BibT_eX]

[DOI]

Paola Campadelli

Mauro Torelli

RAIRO Theor. Informatics Appl., 2006

Separability of rational relations in A* × Nm by recognizable relations is decidable.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2006

Relations over Words and Logic: A Chronology.

[BibT_eX]

Bull. EATCS, 2006

Context-Free Grammars and XML Languages.

[BibT_eX]

[DOI]

Beatrice Palano

Proceedings of the Developments in Language Theory, 10th International Conference, 2006

2005

Collage of two-dimensional words.

[BibT_eX]

[DOI]

Berke Durak

Theor. Comput. Sci., 2005

Preface.

[BibT_eX]

[DOI]

Yoshiko Wakabayashi

RAIRO Theor. Informatics Appl., 2005

Some decision problems on integer matrices.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2005

2004

String-matching with OBDDs.

[BibT_eX]

[DOI]

Yael Haddad

Theor. Comput. Sci., 2004

Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

On the Maximum Coefficients of Rational Formal Series in Commuting Variables.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 2004

Rational Relations as Rational Series.

[BibT_eX]

[DOI]

Proceedings of the Theory Is Forever, 2004

2003

Minimizing subsequential transducers: a survey.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

On the number of occurrences of a symbol in words of regular languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

2002

Distances between languages and reflexivity of relations.

[BibT_eX]

[DOI]

Giovanni Pighizzini

Theor. Comput. Sci., 2002

The commutation of finite sets: a challenging problem.

[BibT_eX]

[DOI]

Nicolas Ollinger

Theor. Comput. Sci., 2002

2001

Long words: the theory of concatenation and omega-power.

[BibT_eX]

[DOI]

Stephen L. Bloom

Theor. Comput. Sci., 2001

Periodicity and roots of transfinite strings.

[BibT_eX]

[DOI]

Olivier Carton

RAIRO Theor. Informatics Appl., 2001

Elementary Theory of Ordinals with Addition and Left Translation by omega.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

On Fatou properties of rational languages.

[BibT_eX]

Proceedings of the Where Mathematics, 2001

2000

Timed Automata with Periodic Clock Constraints.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2000

Transfinite Equations in Transfinite Strings.

[BibT_eX]

[DOI]

Sándor Horváth

Int. J. Algebra Comput., 2000

The Theory of Rational Relations on Transfinite Strings.

[BibT_eX]

Proceedings of the International Colloquium on Words, 2000

1999

Decision Issues on Functions Realized by Finite Automata.

[BibT_eX]

[DOI]

Hratchia Pélibossian

Pierre Simonnet

J. Autom. Lang. Comb., 1999

Determinants and Möbius functions in trace monoids.

[BibT_eX]

[DOI]

Discret. Math., 1999

Uniformization of Rational Relations.

[BibT_eX]

Proceedings of the Jewels are Forever, 1999

1998

Commutativity in Free Inverse Monoids.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Equations in Transfinite Strings.

[BibT_eX]

[DOI]

Sándor Horváth

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997

Combinatorics of Words.

[BibT_eX]

[DOI]

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

A Note on Decidability Questions on Presentations of Word Semigroups.

[BibT_eX]

[DOI]

Tero Harju

Theor. Comput. Sci., 1997

Generalized Rational Relations and their Logical Definability.

[BibT_eX]

[DOI]

Leucio Guerra

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

Constructing Sequential Bijections.

[BibT_eX]

[DOI]

Christophe Prieur

Michel Latteux

Proceedings of the Structures in Logic and Computer Science, 1997

1995

Rational Transductions and Complexity of Counting Problems.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1995

Logical Definability of Some Rational Trace Languages.

[BibT_eX]

[DOI]

Leucio Guerra

Math. Syst. Theory, 1995

Combinatorics in Trace Monoids I.

[BibT_eX]

[DOI]

Proceedings of the Book of Traces, 1995

1994

Bijective Sequential Mappings of a Free Monoid Onto Another.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1994

On Boyer-Moore Automata.

[BibT_eX]

[DOI]

Ricardo A. Baeza-Yates

Gaston H. Gonnet

Algorithmica, 1994

1993

On the Starheight of Some Rational Subsets Closed under Partial Commutations

[BibT_eX]

[DOI]

Inf. Comput., September, 1993

Conjugacy in Free Inverse Monoids.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 1993

1992

Rational Relations and Ratonal Series.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

1991

Conjugacies.

[BibT_eX]

Bull. EATCS, 1991

1990

An Optimal Algorithm for building the Boyer-Moore automaton.

[BibT_eX]

Bull. EATCS, 1990

Iterated Substitutions and Locally Catanative Systems: A Decidability Result in the Binary Case.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1988

Counting with Rational Functions.

[BibT_eX]

[DOI]

Marcel Paul Schützenberger

Theor. Comput. Sci., 1988

1987

A Star-Height Problem in Free Monoids with Partial Communications.

[BibT_eX]

[DOI]

Christine Duboc

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

1986

Décomposition de Fonctions Rationnelles.

[BibT_eX]

[DOI]

Marcel Paul Schützenberger

Proceedings of the STACS 86, 1986

An Introduction to Automata Network Theory.

[BibT_eX]

[DOI]

Proceedings of the Automata Networks, LITP Spring School on Theoretical Computer Science, 1986

1985

Test sets for morphisms with bounded delay.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1985

1984

On extendibility of unavoidable sets.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1984

On Real-Time Cellular Automata and Trellis Automata.

[BibT_eX]

[DOI]

Acta Informatica, 1984

1983

Properties of Finite and Pushdown Transducers.

[BibT_eX]

[DOI]

SIAM J. Comput., 1983

Folding of the Plane and the Design of Systolic Arrays.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1983

1981

A Closure Property of Deterministic Context-Free Languages.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1981

Prefix-Preservation fo Rational Partial Functions Is Decidable.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 1981

1979

A Generalization of Ginsburg and Rose's Characterization of G-S-M Mappings.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1979

1978

Sur les traductions reconnaissables.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1978

1977

Sur Certaines Applications Séquentielles Numériques

[BibT_eX]

[DOI]

Inf. Control., April, 1977

Une Caracterisation des Fonctions Sequentielles et des Fonctions Sous-Sequentielles en tant que Relations Rationnelles.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1977

Applications séquentielles permutables.

[BibT_eX]

J. Inf. Process. Cybern., 1977

1976

Strongly Connected G-S-M Mappings Preserving Conjugation.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1976, 1976

1972

Transducteurs conservant l'imprimitivité du langage d'entrée.

[BibT_eX]