default search action
Christian Choffrut
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [i8]Christian Choffrut:
Message complexity for unary multiautomata systems. CoRR abs/2408.09002 (2024) - [i7]Christian Choffrut:
Unary counting quantifiers do not increase the expressive power of Presburger aritmetic: an alternative shorter proof. CoRR abs/2410.06822 (2024) - 2023
- [i6]Christian Choffrut:
Synchronous orders on the set of integers. CoRR abs/2309.09566 (2023) - 2022
- [j64]Alexis Bès, Christian Choffrut:
Decidability of Definability Issues in the Theory of Real Addition. Fundam. Informaticae 188(1): 15-39 (2022) - 2021
- [j63]Alexis Bès, Christian Choffrut:
Theories of real addition with and without a predicate for integers. Log. Methods Comput. Sci. 17(2) (2021) - 2020
- [c39]Alexis Bès, Christian Choffrut:
$\langle \mathbb {R}, +, <, 1 \rangle $ Is Decidable in $\langle \mathbb {R}, +, < , \mathbb {Z}\rangle $. LATA 2020: 128-140 - [i5]Alexis Bès, Christian Choffrut:
Theories of real addition with and without a predicate for integers. CoRR abs/2002.04282 (2020)
2010 – 2019
- 2019
- [j62]Alexis Bès, Christian Choffrut:
Complexity and (Un)decidability of Fragments of 〈 ω ω λ ;× 〉. Fundam. Informaticae 164(1): 1-15 (2019) - [j61]Benjamin Blanchette, Christian Choffrut, Christophe Reutenauer:
Quasi-automatic semigroups. Theor. Comput. Sci. 777: 111-120 (2019) - [i4]Benjamin Blanchette, Christian Choffrut, Christophe Reutenauer:
Quasi-automatic semigroups. CoRR abs/1906.02842 (2019) - 2018
- [j60]Christian Choffrut, Zoltán Ésik:
Two equational theories of partial words. Theor. Comput. Sci. 737: 19-39 (2018) - [i3]Alexis Bès, Christian Choffrut:
Complexity and (un)decidability of fragments of 〈 ωωλ; × 〉. CoRR abs/1803.01418 (2018) - [i2]Alexis Bès, Christian Choffrut:
Decidability of the existential fragment of some infinitely generated trace monoids: an application to ordinals. CoRR abs/1805.03028 (2018) - 2017
- [j59]Christian Choffrut:
Sequences of words defined by two-way transducers. Theor. Comput. Sci. 658: 85-96 (2017) - [j58]Christian Choffrut:
An Hadamard operation on rational relations. Theor. Comput. Sci. 664: 78-90 (2017) - 2016
- [c38]Christian Choffrut, Bruno Guillon
:
Both Ways Rational Functions. DLT 2016: 114-124 - 2015
- [j57]Christian Choffrut, Serge Grigorieff:
Logical Theory of the Monoid of Languages over a Non Tally Alphabet. Fundam. Informaticae 138(1-2): 159-177 (2015) - [c37]Christian Choffrut, Serge Grigorieff:
Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations. Fields of Logic and Computation II 2015: 109-128 - 2014
- [j56]Christian Choffrut:
Deciding Whether or Not a Synchronous Relation is Regular Prefix. Fundam. Informaticae 132(4): 439-459 (2014) - [j55]Alberto Bertoni, Christian Choffrut, Flavio D'Alessandro:
On the Decidability of the Intersection Problem for Quantum Automata and Context-Free Languages. Int. J. Found. Comput. Sci. 25(8): 1065-1082 (2014) - [c36]Christian Choffrut, Bruno Guillon:
An algebraic characterization of unary two-way transducers. ICTCS 2014: 279-283 - [c35]Christian Choffrut, Bruno Guillon
An Algebraic Characterization of Unary Two-Way Transducers. MFCS (1) 2014: 196-207 - 2013
- [c34]Christian Choffrut, Robert Mercas:
The Lexicographic Cross-Section of the Plactic Monoid Is Regular. WORDS 2013: 83-94 - [c33]Alberto Bertoni, Christian Choffrut, Flavio D'Alessandro:
Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem. Developments in Language Theory 2013: 82-93 - [i1]Alberto Bertoni, Christian Choffrut, Flavio D'Alessandro:
Quantum finite automata and linear context-free languages: a decidable problem. CoRR abs/1303.2967 (2013) - 2012
- [j54]Christian Choffrut, Andreas Malcher
First-order logics: some characterizations and closure properties. Acta Informatica 49(4): 225-248 (2012) - [j53]Christian Choffrut:
A Note on the Logical Definability of Rational Trace Languages. Fundam. Informaticae 116(1-4): 45-50 (2012) - [j52]Christian Choffrut, Serge Grigorieff:
Rational relations having a rational trace on each finite intersection of rational relations. Theor. Comput. Sci. 454: 88-94 (2012) - 2011
- [j51]Alberto Bertoni, Christian Choffrut, Roberto Radicioni:
The Inclusion Problem of Context-Free Languages: Some Tractable Cases. Int. J. Found. Comput. Sci. 22(2): 289-299 (2011) - [j50]Christian Choffrut, Juhani Karhumäki:
Unique Decipherability in the Monoid of Languages: An Application of Rational Relations. Theory Comput. Syst. 49(2): 355-364 (2011) - [c32]Christian Choffrut:
On relations of finite words over infinite alphabets. AFL 2011: 25-27 - 2010
- [j49]Christian Choffrut, Achille Frigeri:
Deciding whether the ordering is necessary in a Presburger formula. Discret. Math. Theor. Comput. Sci. 12(1): 21-38 (2010) - [j48]Christian Choffrut, Robert George Mercas:
Contextual partial commutations. Discret. Math. Theor. Comput. Sci. 12(4): 59-72 (2010) - [j47]Christian Choffrut, Flavio D'Alessandro, Stefano Varricchio:
On Bounded Rational Trace Languages. Theory Comput. Syst. 46(2): 351-369 (2010) - [c31]Christian Choffrut, Andreas Malcher
On the Expressive Power of FO[ + ]. LATA 2010: 190-201
2000 – 2009
- 2009
- [j46]Christian Choffrut, Serge Grigorieff:
Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. Theor. Comput. Sci. 410(1): 16-34 (2009) - [j45]Christian Choffrut, Serge Grigorieff:
The "equal last letter" predicate for words on infinite alphabets and classes of multitape automata. Theor. Comput. Sci. 410(30-32): 2870-2884 (2009) - [c30]Christian Choffrut, Juhani Karhumäki:
Unique Decipherability in the Monoid of Languages: An Application of Rational Relations. CSR 2009: 71-79 - [c29]Alberto Bertoni, Christian Choffrut, Roberto Radicioni:
The Inclusion Problem of Context-Free Languages: Some Tractable Cases. Developments in Language Theory 2009: 103-112 - 2008
- [j44]Christian Choffrut, Loïc Colson:
Preface. RAIRO Theor. Informatics Appl. 42(1): 1-4 (2008) - [j43]Christian Choffrut:
Deciding whether a relation defined in Presburger logic can be defined in weaker logics. RAIRO Theor. Informatics Appl. 42(1): 121-135 (2008) - [c28]Alberto Bertoni, Christian Choffrut, Roberto Radicioni:
Literal Shuffle of Compressed Words. IFIP TCS 2008: 87-100 - 2007
- [j42]Christian Choffrut, Flavio D'Alessandro, Stefano Varricchio:
On the separability of sparse context-free languages and of bounded rational relations. Theor. Comput. Sci. 381(1-3): 274-279 (2007) - [c27]Christian Choffrut, Achille Frigeri:
Definable sets in weak Presburger arithmetic. ICTCS 2007: 175-186 - 2006
- [j41]Christian Choffrut:
Relations over Words and Logic: A Chronology. Bull. EATCS 89: 159-163 (2006) - [j40]Christian Choffrut, Serge Grigorieff:
Separability of rational relations in A* × Nm by recognizable relations is decidable. Inf. Process. Lett. 99(1): 27-32 (2006) - [j39]Paola Campadelli, Christian Choffrut, Massimiliano Goldwurm, Mauro Torelli:
Preface. RAIRO Theor. Informatics Appl. 40(2) (2006) - [j38]Olivier Carton
Decision problems among the main subfamilies of rational relations. RAIRO Theor. Informatics Appl. 40(2): 255-275 (2006) - [j37]Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati
Local Limit Properties for Pattern Statistics and Rational Models. Theory Comput. Syst. 39(1): 209-235 (2006) - [c26]Alberto Bertoni, Christian Choffrut, Beatrice Palano
Context-Free Grammars and XML Languages. Developments in Language Theory 2006: 108-119 - 2005
- [j36]Christian Choffrut, Juhani Karhumäki:
Some decision problems on integer matrices. RAIRO Theor. Informatics Appl. 39(1): 125-131 (2005) - [j35]Christian Choffrut, Yoshiko Wakabayashi
Preface. RAIRO Theor. Informatics Appl. 39(1) (2005) - [j34]Christian Choffrut, Berke Durak:
Collage of two-dimensional words. Theor. Comput. Sci. 340(1): 364-380 (2005) - 2004
- [j33]Christian Choffrut, Yael Haddad:
String-matching with OBDDs. Theor. Comput. Sci. 320(2-3): 187-198 (2004) - [c25]Christian Choffrut:
Rational Relations as Rational Series. Theory Is Forever 2004: 29-34 - [c24]Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati:
On the Maximum Coefficients of Rational Formal Series in Commuting Variables. Developments in Language Theory 2004: 114-126 - [c23]Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati:
Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models. STACS 2004: 117-128 - 2003
- [j32]Christian Choffrut:
Minimizing subsequential transducers: a survey. Theor. Comput. Sci. 292(1): 131-143 (2003) - [j31]Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati
On the number of occurrences of a symbol in words of regular languages. Theor. Comput. Sci. 302(1-3): 431-456 (2003) - 2002
- [j30]Christian Choffrut, Juhani Karhumäki, Nicolas Ollinger:
The commutation of finite sets: a challenging problem. Theor. Comput. Sci. 273(1-2): 69-79 (2002) - [j29]Christian Choffrut, Giovanni Pighizzini
Distances between languages and reflexivity of relations. Theor. Comput. Sci. 286(1): 117-138 (2002) - 2001
- [j28]Olivier Carton, Christian Choffrut:
Periodicity and roots of transfinite strings. RAIRO Theor. Informatics Appl. 35(6): 525-533 (2001) - [j27]Stephen L. Bloom, Christian Choffrut:
Long words: the theory of concatenation and omega-power. Theor. Comput. Sci. 259(1-2): 533-548 (2001) - [c22]Christian Choffrut, Juhani Karhumäki:
On Fatou properties of rational languages. Where Mathematics, Computer Science, Linguistics and Biology Meet 2001: 227-235 - [c21]Christian Choffrut:
Elementary Theory of Ordinals with Addition and Left Translation by omega. Developments in Language Theory 2001: 15-20 - 2000
- [j26]Christian Choffrut, Sándor Horváth:
Transfinite Equations in Transfinite Strings. Int. J. Algebra Comput. 10(5): 625-650 (2000) - [j25]Christian Choffrut, Massimiliano Goldwurm:
Timed Automata with Periodic Clock Constraints. J. Autom. Lang. Comb. 5(4): 371-403 (2000) - [c20]Christian Choffrut, Serge Grigorieff:
The Theory of Rational Relations on Transfinite Strings. Words, Languages & Combinatorics 2000: 103-133
1990 – 1999
- 1999
- [j24]Christian Choffrut, Massimiliano Goldwurm:
Determinants and Möbius functions in trace monoids. Discret. Math. 194(1-3): 239-247 (1999) - [j23]Christian Choffrut, Hratchia Pélibossian, Pierre Simonnet:
Decision Issues on Functions Realized by Finite Automata. J. Autom. Lang. Comb. 4(3): 171-181 (1999) - [c19]Christian Choffrut, Serge Grigorieff:
Uniformization of Rational Relations. Jewels are Forever 1999: 59-71 - 1998
- [j22]Christian Choffrut, Flavio D'Alessandro:
Commutativity in Free Inverse Monoids. Theor. Comput. Sci. 204(1-2): 35-54 (1998) - [c18]Christian Choffrut, Sándor Horváth:
Equations in Transfinite Strings. MFCS 1998: 656-664 - 1997
- [j21]Christian Choffrut, Tero Harju
A Note on Decidability Questions on Presentations of Word Semigroups. Theor. Comput. Sci. 183(1): 83-92 (1997) - [c17]Christophe Prieur, Christian Choffrut, Michel Latteux:
Constructing Sequential Bijections. Structures in Logic and Computer Science 1997: 308-321 - [c16]Christian Choffrut, Leucio Guerra:
Generalized Rational Relations and their Logical Definability. FCT 1997: 138-149 - [c15]Christian Choffrut, Giovanni Pighizzini:
Distances Between Languages and Reflexivity of Relations. MFCS 1997: 199-208 - [p2]Christian Choffrut, Juhani Karhumäki:
Combinatorics of Words. Handbook of Formal Languages (1) 1997: 329-438 - 1995
- [j20]Christian Choffrut, Leucio Guerra:
Logical Definability of Some Rational Trace Languages. Math. Syst. Theory 28(5): 397-420 (1995) - [j19]Christian Choffrut, Massimiliano Goldwurm:
Rational Transductions and Complexity of Counting Problems. Math. Syst. Theory 28(5): 437-450 (1995) - [p1]Christian Choffrut:
Combinatorics in Trace Monoids I. The Book of Traces 1995: 71-82 - 1994
- [j18]Ricardo A. Baeza-Yates
On Boyer-Moore Automata. Algorithmica 12(4/5): 268-292 (1994) - [j17]Christian Choffrut:
Bijective Sequential Mappings of a Free Monoid Onto Another. RAIRO Theor. Informatics Appl. 28(3-4): 265-276 (1994) - 1993
- [j16]Christian Choffrut:
On the Starheight of Some Rational Subsets Closed under Partial Commutations. Inf. Comput. 106(1): 61-82 (1993) - [j15]Christian Choffrut:
Conjugacy in Free Inverse Monoids. Int. J. Algebra Comput. 3(2): 169-188 (1993) - [c14]Christian Choffrut, Leucio Guerra:
On the Logical Definability of Some Rational Trace Languages. STACS 1993: 494-504 - 1992
- [j14]Christian Choffrut:
Rational Relations and Ratonal Series. Theor. Comput. Sci. 98(1): 5-13 (1992) - [c13]Christian Choffrut, Massimiliano Goldwurm:
Rational Transductions and Complexity of Counting Problems. MFCS 1992: 181-190 - 1991
- [j13]Christian Choffrut:
Conjugacies. Bull. EATCS 45: 148-157 (1991) - [c12]Christian Choffrut:
Conjugacy in Free Inverse Monoids. IWWERT 1991: 6-22 - [e3]Christian Choffrut, Matthias Jantzen:
STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, February 14-16, 1991, Proceedings. Lecture Notes in Computer Science 480, Springer 1991, ISBN 3-540-53709-0 [contents] - 1990
- [j12]Christian Choffrut:
An Optimal Algorithm for building the Boyer-Moore automaton. Bull. EATCS 40: 217-224 (1990) - [c11]Christian Choffrut:
Iterated Substitutions and Locally Catanative Systems: A Decidability Result in the Binary Case. ICALP 1990: 490-500 - [e2]Christian Choffrut, Thomas Lengauer:
STACS 90, 7th Annual Symposium on Theoretical Aspects of Computer Science, Rouen, France, February 22-24, 1990, Proceedings. Lecture Notes in Computer Science 415, Springer 1990, ISBN 3-540-52282-4 [contents]
1980 – 1989
- 1988
- [j11]Christian Choffrut, Marcel Paul Schützenberger:
Counting with Rational Functions. Theor. Comput. Sci. 58: 81-101 (1988) - [e1]Christian Choffrut:
Automata Networks, LITP Spring School on Theoretical Computer Science, Angelès-Village, France, May 12-16, 1986, Proceedings. Lecture Notes in Computer Science 316, Springer 1988, ISBN 3-540-19444-4 [contents] - 1987
- [c10]Christian Choffrut, Christine Duboc:
A Star-Height Problem in Free Monoids with Partial Communications. ICALP 1987: 190-201 - 1986
- [c9]Christian Choffrut, Marcel Paul Schützenberger:
Counting with Rational Functions. ICALP 1986: 79-88 - [c8]Christian Choffrut:
An Introduction to Automata Network Theory. Automata Networks 1986: 1-18 - [c7]Christian Choffrut, Marcel Paul Schützenberger:
Décomposition de Fonctions Rationnelles. STACS 1986: 213-226 - 1985
- [j10]Christian Choffrut, Juhani Karhumäki:
Test sets for morphisms with bounded delay. Discret. Appl. Math. 12(2): 93-101 (1985) - 1984
- [j9]Christian Choffrut, Karel Culík II:
On Real-Time Cellular Automata and Trellis Automata. Acta Informatica 21: 393-407 (1984) - [j8]Christian Choffrut, Karel Culík II:
On extendibility of unavoidable sets. Discret. Appl. Math. 9(2): 125-137 (1984) - [c6]Christian Choffrut, Karel Culík II:
On Extendibility of Unavoidable Sets. STACS 1984: 326-338 - 1983
- [j7]Christian Choffrut, Karel Culík II:
Folding of the Plane and the Design of Systolic Arrays. Inf. Process. Lett. 17(3): 149-153 (1983) - [j6]Christian Choffrut, Karel Culík II:
Properties of Finite and Pushdown Transducers. SIAM J. Comput. 12(2): 300-315 (1983) - [c5]Christian Choffrut, Juhani Karhumäki:
Test Sets for Morphisms with Bounded Delay. ICALP 1983: 118-127 - 1981
- [j5]Christian Choffrut:
A Closure Property of Deterministic Context-Free Languages. Inf. Process. Lett. 12(1): 13-16 (1981) - [c4]Christian Choffrut:
Prefix-Preservation fo Rational Partial Functions Is Decidable. Theoretical Computer Science 1981: 159-166
1970 – 1979
- 1979
- [c3]Christian Choffrut:
A Generalization of Ginsburg and Rose's Characterization of G-S-M Mappings. ICALP 1979: 88-103 - 1978
- [j4]Christian Choffrut:
Sur les traductions reconnaissables. RAIRO Theor. Informatics Appl. 12(3): 203-212 (1978) - 1977
- [j3]Christian Choffrut:
Applications séquentielles permutables. J. Inf. Process. Cybern. 13(7/8): 351-357 (1977) - [j2]Christian Choffrut:
Sur Certaines Applications Séquentielles Numériques. Inf. Control. 33(4): 352-363 (1977) - [j1]Christian Choffrut:
Une Caracterisation des Fonctions Sequentielles et des Fonctions Sous-Sequentielles en tant que Relations Rationnelles. Theor. Comput. Sci. 5(3): 325-337 (1977) - 1976
- [c2]Christian Choffrut:
Strongly Connected G-S-M Mappings Preserving Conjugation. MFCS 1976: 224-229 - 1972
- [c1]Christian Choffrut:
Transducteurs conservant l'imprimitivité du langage d'entrée. ICALP 1972: 13-29
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-11-20 22:00 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: