Search

Your search keyword '"Choffrut, Christian"' showing total 315 results
Start Over Author "Choffrut, Christian"
315 results on '"Choffrut, Christian"'

1. Unary counting quantifiers do not increase the expressive power of Presburger aritmetic: an alternative shorter proof

Author

Choffrut, Christian

Subjects
Computer Science - Logic in Computer Science
Abstract

This work was presented in June 5-7, 2017 at the conference "Journ\'{e}es sur les Arithm\'{e}tiques Faibles -- Weak Arithmetics Days" held in Saint-Pertersburg of which no proceeding was ever published. It was not a new result but showed that a different approach is possible. The paper presented at ICALP 2024 addresses, among other problems, the complexity issues which were ignored in my 2017 talk.

Published
2024

2. Message complexity for unary multiautomata systems

Author

Choffrut, Christian

Subjects
Computer Science - Logic in Computer Science, Computer Science - Formal Languages and Automata Theory
Abstract

Finitely many two-way automata work independently and synchronously on a unary input. Some of their states are broadcasting, i.e., dispatched to all other automata. At each step of the computation, each automaton changes state and moves right, left or stay in place according to the current state and the possible messages dispatched. The input is recognized if the following occurs: starting from the initial configuration (the heads of all automata are positioned to the left end of the tape) one automaton reaches a final state when its head is positioned to the right end of the tape. We show that if the number of messages sent during the computation is bounded by some integer which is independent of the length of the input, then the language recognized is regular

Published
2024

3. Equational theory of ordinals with addition and left multiplication by $\omega$

Author

Choffrut, Christian

Subjects
Mathematics - Logic
Abstract

We show that the equational theory of the structure $\langle \omega^{\omega}: (x,y)\mapsto x+y, x\mapsto \omega x \rangle $ is finitely axiomatizable and give a simple axiom schema when the domain is the set of transfinite ordinals. We give an algorithm that given a pair of terms $(E,F)$ decides in linear time with respect of their common length whether or not $E=F$ is a consequence of the axioms.

Published
2024

4. Synchronous orders on the set of integers

Author

Choffrut, Christian

Subjects
Computer Science - Formal Languages and Automata Theory, F.4
Abstract

A binary relation over a free monoid is synchronous if it can be recognized by a synchronous automaton that reads its two tapes simultaneously. We consider the case where the free monoid is generated by a single element (which makes it isomorphic to the additive monoid of integers) and where the binary relation recognized is a strict order. Our main results are: given such an automaton it is possible to determine whether or not is has infinite chains or antichains; we characterize the orders that are linear; given two linear synchronous orders we show how to determine whether or not they are equivalent.

Published
2023

5. Grammic monoids with three generators

Author

Choffrut, Christian

Subjects
Mathematics - Combinatorics
Abstract

Young tableaux are combinatorial objects whose construction can be achieved from words over a finite alphabet by row or column insertion as shown by Schensted sixty years ago. Recently Abram and Reutenauer studied the action the free monoid on the set of columns by slightly adapting the insertion algorithm. Since the number of columns is finite, this action yields a finite transformation monoid. Here we consider the action on the set of rows. We investigate this infinite monoid in the case of a 3 letter alphabet. In particular we show that it is the quotient of the free monoid relative to a congruence generated by the classical Knuth rules plus a unique extra rule.

Published
2022

6. Decidability of definability issues in the theory of real addition

Author

Bès, Alexis and Choffrut, Christian

Subjects
Mathematics - Logic
Abstract

Given a subset of $X\subseteq \mathbb{R}^{n}$ we can associate with every point $x\in \mathbb{R}^{n}$ a vector space $V$ of maximal dimension with the property that for some ball centered at $x$, the subset $X$ coincides inside the ball with a union of lines parallel with $V$. A point is singular if $V$ has dimension $0$. In an earlier paper we proved that a $(\mathbb{R}, +,< ,\mathbb{Z})$-definable relation $X$ is actually definable in $(\mathbb{R}, +,< ,1)$ if and only if the number of singular points is finite and every rational section of $X$ is $(\mathbb{R}, +,< ,1)$-definable, where a rational section is a set obtained from $X$ by fixing some component to a rational value. Here we show that we can dispense with the hypothesis of $X$ being $(\mathbb{R}, +,< ,\mathbb{Z})$-definable by assuming that the components of the singular points are rational numbers. This provides a topological characterization of first-order definability in the structure $(\mathbb{R}, +,< ,1)$. It also allows us to deliver a self-definable criterion (in Muchnik's terminology) of $(\mathbb{R}, +,< ,1)$- and $(\mathbb{R}, +,< ,\mathbb{Z})$-definability for a wide class of relations, which turns into an effective criterion provided that the corresponding theory is decidable. In particular these results apply to the class of $k-$recognizable relations on reals, and allow us to prove that it is decidable whether a $k-$recognizable relation (of any arity) is $l-$recognizable for every base $l \geq 2$.

Published
2021

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

Author

Bès, Alexis and Choffrut, Christian

Subjects
Computer Science - Logic in Computer Science, Mathematics - Logic
Abstract

We show that it is decidable whether or not a relation on the reals definable in the structure $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$ can be defined in the structure $\langle \mathbb{R}, +,<, 1 \rangle$. This result is achieved by obtaining a topological characterization of $\langle \mathbb{R}, +,<, 1 \rangle$-definable relations in the family of $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$-definable relations and then by following Muchnik's approach of showing that the characterization of the relation $X$ can be expressed in the logic of $\langle \mathbb{R}, +,<,1, X \rangle$. The above characterization allows us to prove that there is no intermediate structure between $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$ and $\langle \mathbb{R}, +,<, 1 \rangle$. We also show that a $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$-definable relation is $\langle \mathbb{R}, +,<, 1 \rangle$-definable if and only if its intersection with every $\langle \mathbb{R}, +,<, 1 \rangle$-definable line is $\langle \mathbb{R}, +,<, 1 \rangle$-definable. This gives a noneffective but simple characterization of $\langle \mathbb{R}, +,<, 1 \rangle$-definable relations.

Published
2020
Full Text
View/download PDF

8. Quasi-automatic semigroups

Author

Blanchette, Benjamin, Choffrut, Christian, and Reutenauer, Christophe

Subjects
Mathematics - Group Theory, Computer Science - Computational Complexity, Computer Science - Formal Languages and Automata Theory, Mathematics - Combinatorics
Abstract

A quasi-automatic semigroup is defined by a finite set of generators, a rational (regular) set of representatives, such that if a is a generator or neutral, then the graph of right multiplication by a on the set of representatives is a rational relation. This class of semigroups contains previously considered semigroups and groups (Sakarovitch, Epstein et al., Campbell et al.). Membership of a semigroup to this class does not depend on the choice of the generators. These semigroups are rationally presented. Representatives may be computed in exponential time. Their word problem is decidable in exponential time. They enjoy a property similar to the so-called Lipschitz property, or fellow traveler property. If graded, they are automatic. In the case of groups, they are finitely presented with an exponential isoperimetric inequality and they are characterized by the weak Lipschitz property., Comment: 17 pages. In press. Theoretical Computer Science, 2019

Published
2019
Full Text
View/download PDF

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

Author

Bès, Alexis and Choffrut, Christian

Subjects
Computer Science - Logic in Computer Science, Mathematics - Logic
Abstract

Diekert, Matiyasevich and Muscholl proved that the existential first-order theory of a trace monoid over a finite alphabet is decidable. We extend this result to a natural class of trace monoids with infinitely many generators. As an application, we prove that for every ordinal $\lambda$ less than $\varepsilon_0$, the existential theory of the set of successor ordinals less than $\lambda$ equipped with multiplication is decidable.

Published
2018

10. Complexity and (un)decidability of fragments of $\langle \omega^{\omega^\lambda}; \times \rangle$

Author

Bès, Alexis and Choffrut, Christian

Subjects
Computer Science - Logic in Computer Science, Mathematics - Logic
Abstract

We specify the frontier of decidability for fragments of the first-order theory of ordinal multiplication. We give a NEXPTIME lower bound for the complexity of the existential fragment of $\langle \omega^{\omega^\lambda}; \times, \omega, \omega+1, \omega^2+1 \rangle$ for every ordinal $\lambda$. Moreover, we prove (by reduction from Hilbert Tenth Problem) that the $\exists^*\forall^{6}$-fragment of $\langle \omega^{\omega^\lambda}; \times \rangle$ is undecidable for every ordinal $\lambda$.

Published
2018

11. [Untitled]

Author

Bès, Alexis, Choffrut, Christian, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Leporati, Alberto, editor, Martín-Vide, Carlos, editor, Shapira, Dana, editor, and Zandron, Claudio, editor

Published
2020
Full Text
View/download PDF

13. Both Ways Rational Functions

Author

Choffrut, Christian, Guillon, Bruno, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Brlek, Srečko, editor, and Reutenauer, Christophe, editor

Published
2016
Full Text
View/download PDF

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

Author

Choffrut, Christian, Grigorieff, Serge, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Beklemishev, Lev D., editor, Blass, Andreas, editor, Dershowitz, Nachum, editor, Finkbeiner, Bernd, editor, and Schulte, Wolfram, editor

Published
2015
Full Text
View/download PDF

16. An Algebraic Characterization of Unary Two-Way Transducers

Author

Choffrut, Christian, Guillon, Bruno, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Csuhaj-Varjú, Erzsébet, editor, Dietzfelbinger, Martin, editor, and Ésik, Zoltán, editor

Published
2014
Full Text
View/download PDF

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

Author

Choffrut, Christian, Mercaş, Robert, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Karhumäki, Juhani, editor, Lepistö, Arto, editor, and Zamboni, Luca, editor

Published
2013
Full Text
View/download PDF

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

Author

Bertoni, Alberto, Choffrut, Christian, D’Alessandro, Flavio, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Béal, Marie-Pierre, editor, and Carton, Olivier, editor

Published
2013
Full Text
View/download PDF

22. On the Expressive Power of FO[ + ]

Author

Choffrut, Christian, Malcher, Andreas, Mereghetti, Carlo, Palano, Beatrice, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dediu, Adrian-Horia, editor, Fernau, Henning, editor, and Martín-Vide, Carlos, editor

Published
2010
Full Text
View/download PDF

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

Author

Choffrut, Christian, Karhumäki, Juhani, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Frid, Anna, editor, Morozov, Andrey, editor, Rybalchenko, Andrey, editor, and Wagner, Klaus W., editor

Published
2009
Full Text
View/download PDF

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

Author

Bertoni, Alberto, Choffrut, Christian, Radicioni, Roberto, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Diekert, Volker, editor, and Nowotka, Dirk, editor

Published
2009
Full Text
View/download PDF

26. Context-Free Grammars and XML Languages

Author

Bertoni, Alberto, Choffrut, Christian, Palano, Beatrice, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ibarra, Oscar H., editor, and Dang, Zhe, editor

Published
2006
Full Text
View/download PDF

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

Author

Choffrut, Christian, Goldwurm, Massimiliano, Lonati, Violetta, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Calude, Cristian S., editor, Calude, Elena, editor, and Dinneen, Michael J., editor

Published
2005
Full Text
View/download PDF

28. Rational Relations as Rational Series

Author

Choffrut, Christian, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Karhumäki, Juhani, editor, Maurer, Hermann, editor, Păun, Gheorghe, editor, and Rozenberg, Grzegorz, editor

Published
2004
Full Text
View/download PDF

35. documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \mathbb {R}, +,<,1 \rangle $$\end{document} Is Decidable in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \mathbb {R}, +,< ,\mathbb {Z}\rangle $$\end{document}

Author

Bès, Alexis and Choffrut, Christian

Subjects
Article
Abstract

We show that it is decidable whether or not a relation on the reals definable in the structure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \mathbb {R}, +,< ,\mathbb {Z}\rangle $$\end{document} can be defined in the structure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \mathbb {R}, +

Published
2020

36. Equations in transfinite strings

Author

Choffrut, Christian, Horvath, Sandor, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Brim, Luboš, editor, Gruska, Jozef, editor, and Zlatuška, Jiří, editor

Published
1998
Full Text
View/download PDF

39. Constructing sequential bijections

Author

Prieur, Christophe, Choffrut, Christian, Latteux, Michel, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Mycielski, Jan, editor, Rozenberg, Grzegorz, editor, and Salomaa, Arto, editor

Published
1997
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results