Preprints

[1]

Pierre Guillon and Emmanuel Jeandel.
Infinite Communication Complexity.
preprint.
[ Download ]
[Show abstract]
Suppose that Alice and Bob are given each an infinite string, and they want to decide whether their two strings are in a given relation. How much communication do they need? How can communication be even defined and measured for infinite strings? In this article, we propose a formalism for a notion of infinite communication complexity, prove that it satisfies some natural properties and coincides, for relevant applications, with the classical notion of amortized communication complexity. Moreover, an application is given for tackling some conjecture about tilings and multidimensional sofic shifts.

[2]

Emmanuel Jeandel.
Some Notes about Subshifts on Groups.
preprint.
[ Download ]
[Show abstract]
In this note we prove the following results: • If a
finitely presented group G admits a strongly aperiodic SFT, then G has decidable word problem. • For a large class of group G, Z × G admits a strongly aperiodic SFT. In particular, this is true for the free group with 2 generators, Thompson's groups T and V , PSL2(Z) and any f.g. group of rational matrices which is bounded.

[3]

Emmanuel Jeandel and Michael Rao.
An aperiodic set of 11 Wang tiles.
preprint.
[ Download ]
[Show abstract]
A new aperiodic tile set containing 11 Wang tiles on 4 colors is presented. This tile set is minimal in the sense that no Wang set with less than 11 tiles is aperiodic, and no Wang set with less than 4 colors is aperiodic.

[4]

Emmanuel Jeandel.
Translationlike Actions and Aperiodic Subshifts on Groups.
preprint.
[ Download ]
[Show abstract]
It is well known that if G admits a f.g. subgroup H
with a weakly aperiodic SFT (resp. an undecidable domino problem), then
G itself has a weakly aperiodic SFT (resp. an undecidable domino problem).
We prove that we can replace the property `H is a subgroup of G' by `
H acts translationlike on G', provided H is finitely presented.
In particular: * If G_{1} and G_{2} are f.g. infinite groups,
then G_{1}×G_{2} has a weakly aperiodic SFT (and actually an
undecidable domino problem). In particular the Grigorchuk group has
an undecidable domino problem. * Every infinite f.g. pgroup admits a
weakly aperiodic SFT.

[5]

Emmanuel Jeandel, Etienne Moutot, and Pascal Vanier.
Slopes of multidimensional subshifts.
preprint.
Book Chapters

[1]

Nathalie Aubrun, Sebastian Barbieri, and Emmanuel Jeandel.
Sequences, Groups, and Number Theory, chapter About the Domino
Problem for Subshifts on Groups, pages 331389.
Trends in Mathematics. Springer, 2018.
[ DOI ]

[2]

Emmanuel Jeandel and Pascal Vanier.
Tiling Dynamical System, chapter The Undecidability of the
Domino Problem.
To appear.
Papers

[1]

Emmanuel Jeandel and Pascal Vanier.
Characterizations of periods of multidimensional shifts.
Ergodic Theory and Dynamical Systems, 35(2):431460, April
2015.
[ DOI 
Preprint ]
[Show abstract]
We show that the sets of periods of multidimensional
shifts of finite type are precisely the sets of integers of the complexity class NP. We also show that the functions counting their number are the functions of #P. We also give characterizations of some other notions of periodicity in terms of space complexity. We finish the paper by giving some characterizations for sofic and effective subshifts.

[2]

Emmanuel Jeandel and Pascal Vanier.
Hardness of conjugacy, embedding and factorization of
multidimensional subshifts.
Journal of Computer and System Sciences, 81(8):16481664,
2015.
[ DOI 
Preprint ]
[Show abstract]
Subshifts of finite type are sets of colorings of the plane
defined by local constraints. They can be seen as a discretization of
continuous dynamical systems. We investigate here the hardness of deciding
factorization, conjugacy and embedding of subshifts in dimensions
d>1 for subshifts of finite type and sofic shifts and in dimensions
d>0 for effective shifts. In particular, we prove that the conjugacy,
factorization and embedding problems are Σ_{3}^{0}complete for
sofic and effective subshifts and that they are Σ_{1}^{0}complete
for SFTs, except for factorization which is also
Σ_{3}^{0}complete.

[3]

Emmanuel Jeandel and Guillaume Theyssier.
Subshifts as models for MSO logic.
Information and Computation, 225:115, 2013.
[ DOI 
Preprint ]
[Show abstract]
We study the Monadic Second Order (MSO) Hierarchy over
colorings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a characterization of existential MSO in terms of projections of tilings, and of universal sentences in terms of combinations of “pattern counting” subshifts. Conversely, we characterize logic fragments corresponding to various classes of subshifts (subshifts of finite type, sofic subshifts, all subshifts). Finally, we show by a separation result how the situation here is different from the case of tiling pictures studied earlier by Giammarresi et al.

[4]

Emmanuel Jeandel and Pascal Vanier.
Turing degrees of multidimensional SFTs.
Theoretical Computer Science, 505:8192, 2013.
[ DOI 
Preprint ]
[Show abstract]
In this paper we are interested in computability aspects
of subshifts and in particular Turing degrees of 2dimensional SFTs (i.e. tilings). To be more precise, we prove that given any subset P of {0,1}^{ℕ} there is a SFT X such that P×ℤ^{2} is recursively homeomorphic to XU where U is a computable set of points. As a consequence, if P contains a recursive member, P and X have the exact same set of Turing degrees. On the other hand, we prove that if X contains only nonrecursive members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs.

[5]

Emmanuel Jeandel.
The periodic domino problem revisited.
Theoretical Computer Science, 411:40104016, 2010.
[ DOI 
Preprint ]
[Show abstract]
In this article, we give a new proof of the undecidability of
the periodic domino problem. Compared to previous proofs, the main
difference is that this one does not start from a proof of the
undecidability of the (general) domino problem but only from the existence of an aperiodic tileset.

[6]

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, and Stéphan
Thomassé.
Finding a Vector Orthogonal to Roughly Half a Collection of
Vectors.
Journal of Complexity, 24(1):3953, February 2008.
[ DOI 
Research Report ]
[Show abstract]
Dimitri Grigoriev has shown that for any family of N vectors
in the ddimensional linear space E=(F_{2})^{d}, there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of the family. We show that the range [N/3,2N/3] can be replaced by the much smaller range [N/2√N/2,N/2+√N/2] and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.

[7]

Emmanuel Jeandel and Nicolas Ollinger.
Playing with Conway's Problem.
Theoretical Computer Science, 409:557564, 2008.
[ DOI 
Research Report ]
[Show abstract]
The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in 1971, whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc 2005, a strong negative answer to this problem was given by showing that even complete corecursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.

[8]

Emmanuel Jeandel.
Topological Automata.
Theory of Computing Systems, 40(4):397407, June 2007.
[ DOI 
Preprint ]
[Show abstract]
We give here a new, topological, definition of automata that extends previous definitions of probabilistic and quantum automata. We then prove in an unified framework that deterministic or nondeterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.

[9]

Harm Derksen, Emmanuel Jeandel, and Pascal Koiran.
Quantum automata and algebraic groups.
Journal of Symbolic Computation, 39(34):357371,
MarchApril 2005.
[ DOI 
Research Report ]
[Show abstract]
We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices.

[10]

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier.
Decidable and Undecidable Problems about Quantum Automata.
SIAM Journal on Computing, 34(6):14641473, 2005.
[ DOI 
Research Report ]
[Show abstract]
We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and nonstrict thresholds both lead to undecidable problems.
Proceedings

[1]

Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
A Generic Normal Form for ZXDiagrams and Application to the
Rational Angle Completeness.
In ACM/IEEE Symposium on Logic in Computer Science (LICS),
2019.
arXiv:1805.05296.

[2]

Emmanuel Jeandel and Pascal Vanier.
A characterization of subshifts with a computable language.
In Symposium on Theoretical Aspects of Computer Science
(STACS), volume 126, pages 40:140:16, 2019.
[ DOI ]
[Show abstract]
Subshifts are sets of colorings of ℤ^{d} by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by the first author. In particular we prove several theorems on subshifts inspired by Higman's embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type.

[3]

Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, and Pascal Vanier.
Undecidable word problem in subshift automorphism groups.
In International Computer Science Symposium in Russia (CSR),
2019.

[4]

Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
A Complete Axiomatisation of the ZXCalculus for
Clifford+T Quantum Mechanics.
In ACM/IEEE Symposium on Logic in Computer Science (LICS),
pages 559568, 2018.
[ DOI 
Preprint ]
[Show abstract]
We introduce the first complete and approximatively universal diagrammatic language for quantum mechanics. We make the ZXCalculus, a diagrammatic language introduced by Coecke and Duncan, complete for the socalled Clifford+T quantum mechanics by adding four new axioms to the language. The completeness of the ZXCalculus for Clifford+T quantum mechanics was one of the main open questions in categorical quantum mechanics. We prove the completeness of the Clifford+T fragment of the ZXCalculus using the recently studied ZWCalculus, a calculus dealing with integer matrices. We also prove that the Clifford+T fragment of the ZXCalculus represents exactly all the matrices over some finite dimensional extension of the ring of dyadic rationals.

[5]

Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
Diagrammatic Reasoning beyond Clifford+T Quantum Mechanics.
In ACM/IEEE Symposium on Logic in Computer Science (LICS),
pages 569578, 2018.
[ DOI 
Preprint ]
[Show abstract]
The ZXCalculus is a graphical language for quantum mechanics. An axiomatisation has recently been proven to be complete for an approximatively universal fragment of quantum mechanics, the socalled Clifford+T fragment. We focus here on the expressive power of this axiomatisation beyond Clifford+T Quantum mechanics. We consider the full pure qubit quantum mechanics, and mainly prove two results: (i) First, the axiomatisation for Clifford+T quantum mechanics is also complete for all equations involving some kind of linear diagrams. The linearity of the diagrams reflects the phase group structure, an essential feature of the ZXcalculus. In particular all the axioms of the ZXcalculus are involving linear diagrams. (ii) We also show that the axiomatisation for Clifford+T is not complete in general but can be completed by adding a single (non linear) axiom, providing a simpler axiomatisation of the ZXcalculus for pure quantum mechanics than the one recently introduced by Ng&Wang.

[6]

Emmanuel Jeandel.
Enumeration Reducibility in Closure Spaces with Applications to
Logic and Algebra.
In ACM/IEEE Symposium on Logic in Computer Science (LICS),
2017.
[ DOI 
Preprint ]
[Show abstract]
In many instances in first order logic or computable algebra, classical theorems show that many problems are undecidable for general structures, but become decidable if some rigidity is imposed on the structure. For example, the set of theorems in many finitely axiomatisable theories is nonrecursive, but the set of theorems for any finitely axiomatisable complete theory is recursive. Finitely presented groups might have an nonrecursive word problem, but finitely presented simple groups have a recursive word problem. In this article we introduce a topological framework based on closure spaces to show that many of these proofs can be obtained in a similar setting. We will show in particular that these statements can be generalized to cover arbitrary structures, with no finite or recursive presentation/axiomatization. This generalizes in particular work by Kuznetsov and others. Examples from first order logic and symbolic dynamics will be discussed at length.

[7]

Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
YCalculus: A language for real Matrices derived from the
ZXCalculus.
In International Conference on Quantum Physics and Logic (QPL),
number 266 in Electronic Proceedings in Theoretical Computer Science, pages
2357, 2017.
[ DOI ]
[Show abstract]
We introduce a ZXlike diagrammatic language devoted to manipulating real matrices (and rebits), with its own set of axioms. We prove the necessity of some non trivial axioms of these. We show that some restriction of the language is complete. We exhibit two interpretations to and from the ZXCalculus, thus showing the consistency between the two languages. Finally, we derive from our work a way to extract the real or imaginary part of a ZXdiagram, and prove that a restriction of our language is complete if the equivalent restriction of the ZXcalculus is complete.

[8]

Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, and Quanlong Wang.
ZXCalculus: Cyclotomic Supplementarity and Incompleteness for
Clifford+T quantum mechanics.
In Mathematical Foundations of Computer Science (MFCS),
number 83 in LIPIcs, pages 11:1  11:13, 2017.
[ DOI ]
[Show abstract]
The ZXCalculus is a powerful graphical language for quantum mechanics and quantum information processing. The completeness of the language  i.e. the ability to derive any true equation  is a crucial question. In the quest of a complete ZXcalculus, supplementarity has been recently proved to be necessary for quantum diagram reasoning (MFCS 2016). Roughly speaking, supplementarity consists in merging two subdiagrams when they are parameterized by antipodal angles. We introduce a generalised supplementarity  called cyclotomic supplementarity  which consists in merging n subdiagrams at once, when the n angles divide the circle into equal parts. We show that when n is an odd prime number, the cyclotomic supplementarity cannot be derived, leading to a countable family of new axioms for diagrammatic quantum reasoning. We exhibit another new simple axiom that cannot be derived from the existing rules of the ZXCalculus, implying in particular the incompleteness of the language for the socalled Clifford+T quantum mechanics. We end up with a new axiomatisation of an extended ZXCalculus, including an axiom schema for the cyclotomic supplementarity.

[9]

Emmanuel Jeandel.
Computability in Symbolic Dynamics.
In Computability in Europe (CiE), volume 9709 of Lecture
Notes in Computer Science, pages 124131, 2016.
Invited talk.
[ DOI ]
[Show abstract]
We give an overview of the interplay between computability and symbolic dynamics.

[10]

Emmanuel Jeandel.
Computability of the entropy of onetape Turing machines.
In Symposium on Theoretical Aspects of Computer Science
(STACS), volume 25, pages 421432, 2014.
[ DOI ]
[Show abstract]
We prove that the maximum speed and the entropy of a onetape Turing machine are computable, in the sense that we can approximate them to any given precision . This is counterintuitive, as all dynamical properties are usually undecidable for Turing machines. The result is quite specific to onetape Turing machines, as it is not true anymore for twotape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.

[11]

Emmanuel Jeandel and Pascal Vanier.
Hardness of conjugacy and factorization of multidimensional
subshifts of finite type.
In Symposium on Theoretical Aspects of Computer Science
(STACS), volume 20, pages 490501, 2013.
[ DOI 
Preprint ]
[Show abstract]
We investigate here the hardness of conjugacy and
factorization of subshifts of finite type (SFTs) in dimension d>1. In particular, we prove that the factorization problem is Σ^{0}_{3}complete and the conjugacy problem Σ^{0}_{1}complete in the arithmetical hierarchy.

[12]

Emmanuel Jeandel and Nicolas Rolin.
Fixed Parameter Undecidability for Wang Tilesets.
In Symposium on Cellular Automata (JAC), pages 6985, 2012.
[ DOI ]
[Show abstract]
Deciding if a given set of Wang tiles admits a tiling of the plane is decidable if the number of Wang tiles (or the number of colors) is bounded, for a trivial reason, as there are only finitely many such tilesets. We prove however that the tiling problem remains undecidable if the difference between the number of tiles and the number of colors is bounded by 43.
One of the main new tool is the concept of Wang bars, which are
equivalently inflated Wang tiles or thin polyominoes.

[13]

Emmanuel Jeandel.
On Immortal configurations in Turing machines.
In Computability in Europe (CiE), volume 7318 of Lecture
Notes in Computer Science, pages 334343, 2012.
[ DOI 
Preprint ]
[Show abstract]
We investigate the immortality problem for Turing
machines and prove that there exists a Turing Machine that is
immortal but halts on every recursive configuration. The result is obtained by combining a new proof of Hooper?s theorem [11] with recent results on effective symbolic dynamics.

[14]

Emmanuel Jeandel and Pascal Vanier.
Π_{1}^{0} sets and tilings.
In Theory and Applications of Models of Computation (TAMC),
volume 6648 of Lecture Notes in Computer Science, pages 230239, 2011.
[ DOI 
Preprint ]
[Show abstract]
In this paper, we prove that given any Π_{1}^{0} subset
P of {0,1}^{ℕ} there is a tileset τ with a set of configurations
C such that P ×ℤ^{2} is recursively homeomorphic to CU where U is a computable set of configurations.
As a consequence, if P is countable, this tileset has the exact
same set of Turing degrees.

[15]

Emmanuel Jeandel and Pascal Vanier.
Slopes of tilings.
In Symposium on Cellular Automata (JAC), pages 145155, 2010.
[ Download ]
[Show abstract]
We study here slopes of periodicity of tilings.
A tiling is of slope θ if it is periodic along direction
θ but has no other direction of periodicity.
We characterize in this paper the set of slopes we can achieve with tilings, and prove they coincide with recursively enumerable sets of rationals.

[16]

Alexis Ballier and Emmanuel Jeandel.
Computing (or not) quasiperiodicity functions of tilings.
In Symposium on Cellular Automata (JAC), pages 5464, 2010.
[ Download ]
[Show abstract]
We know that tilesets that can tile the plane always admit a quasiperiodic
tiling, yet they hold many uncomputable
properties.
The quasiperiodicity function is one way to measure the regularity of a
quasiperiodic tiling.
We prove that the tilings by a tileset that admits only quasiperiodic tilings
have a recursively (and uniformly) bounded quasiperiodicity function.
This corrects an error from [CervelleDurand2004] which stated the
contrary.
Instead we construct a tileset for which any quasiperiodic tiling has a
quasiperiodicity function that cannot be recursively bounded.
We provide such a construction for 1dimensional effective subshifts and
obtain as a corollary the result for tilings of the plane via recent
links between these objects.

[17]

Emmanuel Jeandel and Pascal Vanier.
Periodicity in Tilings.
In Developments in Language Theory (DLT), volume 6224 of
Lecture Notes in Computer Science, pages 243254. Springer, 2010.
[ DOI 
Preprint ]
[Show abstract]
Tilings and tiling systems are an abstract concept that arise
both as a computational model and as a dynamical system. In this paper, we
prove an analog of the theorems of Fagin [9] and Selman and Jones [14] by characterizing sets of periods of tiling systems by complexity classes.

[18]

Alexis Ballier, Bruno Durand, and Emmanuel Jeandel.
Tilings robust to errors.
In Latin American Theoretical Informatics Symposium (LATIN),
volume 6034 of Lecture Notes in Computer Science, pages 480491.
Springer, 2010.
[ DOI 
Preprint ]
[Show abstract]
We study the error robustness of tilings of the plane.
The fundamental question is the following: given a tileset, what happens
if we allow a small probability of errors? Are the objects we obtain
close to an errorfree tiling of the plane?
We prove that tilesets that produce only periodic tilings are robust to
errors; for this proof, we use a hierarchical construction of islands of
errors. We also show that another class of tilesets, those that admit
countably many tilings is not robust and that there is no computable
way to distinguish between these two classes.

[19]

Emmanuel Jeandel and Guillaume Theyssier.
Subshifts, Languages and Logic.
In Developments in Language Theory (DLT), volume 5583 of
Lecture Notes in Computer Science, pages 288299. Springer, 2009.
[ DOI 
Preprint ]
[Show abstract]
We study the Monadic Second Order (MSO) Hierarchy over
infinite pictures, that is tilings. We give a characterization of existential
MSO in terms of tilings and projections of tilings. Conversely, we characterise logic fragments corresponding to various classes of infinite pictures
(subshifts of finite type, sofic subshifts).

[20]

Alexis Ballier and Emmanuel Jeandel.
Tilings and Model Theory.
In Symposium on Cellular Automata Journées Automates
Cellulaires (JAC), pages 2939, Moscow, 2008. MCCME Publishing House.
[ Download ]
[Show abstract]
In this paper we emphasize the links between model theory and tilings. More
precisely, after giving the definitions of what tilings are, we give a natural way to have
an interpretation of the tiling rules in first order logics. This opens the way to map some
model theoretical properties onto some properties of sets of tilings, or
tilings themselves.

[21]

Alexis Ballier, Bruno Durand, and Emmanuel Jeandel.
Structural Aspects of Tilings.
In Symposium on Theoretical Aspects of Computer Science
(STACS), pages 6172. Schloss Dagstuhl  LeibnizZentrum fuer Informatik,
Germany, 2008.
[ DOI 
Download ]
[Show abstract]
In this paper, we study the structure of
the set of tilings produced by any given tileset.
For better understanding this structure, we address the set of finite
patterns that each tiling contains.
This set of patterns can be analyzed in two different contexts: the first one is
combinatorial and the other topological. These two approaches have
independent merits and, once combined, provide somehow surprising
results.
The particular case where the set of produced tilings is countable is
deeply investigated while we prove that the uncountable case may have a
completely different structure.
We introduce a pattern preorder and also make use of CantorBendixson rank.
Our first main result is that a tileset that produces only periodic tilings
produces only a finite number of them. Our second main result exhibits a tiling with
exactly one vector of periodicity in the countable case.

[22]

Emmanuel Jeandel.
Topological Automata.
In Symposium on Theoretical Aspects of Computer Science
(STACS), volume 3404 of Lecture Notes in Computer Science, pages
389398. Springer, 2005.
[ DOI 
Preprint ]
[Show abstract]
We give here a new, topological, definition of automata that extends previous definitions of probabilistic and quantum automata. We then prove in an unified framework that deterministic or nondeterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.

[23]

Emmanuel Jeandel.
Universality in Quantum Computation.
In International Colloquium on Automata, Languages and
Programming (ICALP), volume 3142 of Lecture Notes in Computer Science,
pages 793804. Springer, 2004.
[ DOI 
Preprint ]
[Show abstract]
" We introduce several new definitions of universality for sets of
quantum gates, and prove separation results for these definitions.
In particular, we prove that realisability with ancillas is
different from the classical notion of completeness. We give a
polynomial time algorithm of independent interest which decides if a
subgroup of a classical group (SO_{n}, SU_{n}, SL_{n}) is Zariski dense,
thus solving the decision problem for the completeness. We also
present partial methods for the realisability with ancillas."
(Published) Posters

[1]

Frederic Grosshans, Ruben Y. Cohen, Emmanuel Jeandel, and Simon Perdrix.
Entanglement Distribution Across a Quantum PeertoPeer
Network.
In Quantum Information and Measurement (QIM), Optical Society
of America Technical Digest, page QT6A.21, 2017.
[ DOI ]
Research Reports

[1]

Emmanuel Jeandel.
Computability of the entropy of onetape Turing Machines.
Technical Report hal00785232, Universite de Lorraine, 2013.
[ Download ]

[2]

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, and Stéphan
Thomassé.
Finding a Vector Orthogonal to Roughly Half a Collection of
Vectors.
Technical Report RR200605, LIP, ENS Lyon, January 2006.
[ Download ]
[Show abstract]
Dimitri Grigoriev has shown that for any family of N vectors
in the ddimensional linear space E=(F_{2}^{d}), there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of the family. We show that the range [N/3,2N/3] can be replaced by the much smaller range [N/2√N/2,N/2+√N/2] and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.

[3]

Emmanuel Jeandel and Nicolas Ollinger.
Playing with Conway's Problem.
Technical Report ccsd00013788, Laboratoire d'informatique
Fondamentale de Marseille, 2005.
[ Download ]
[Show abstract]
The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in 1971, whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc 2005, a strong negative answer to this problem was given by showing that even complete corecursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.

[4]

Harm Derksen, Emmanuel Jeandel, and Pascal Koiran.
Quantum automata and algebraic groups.
Technical Report RR200339, LIP, ENS Lyon, July 2003.
[ Download ]
[Show abstract]
We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices.

[5]

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier.
Decidable and undecidable problems about quantum automata.
Technical Report RR200324, LIP, ENS Lyon, April 2003.
[ Download ]
[Show abstract]
We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and nonstrict thresholds both lead to undecidable problems.

[6]

Emmanuel Jeandel.
valuation rapide de fonctions hypergomtriques.
Technical Report RT0242, INRIA  ENS Lyon, 2000.
[ Download ]
[Show abstract]
Nous prsentons ici l'implantation des fonctions
hypergomtriques dans la bibliothque MPFR. Ceci a t effectu l'aide de la mthode Binary Splitting. Un algorithme gnrique a donc t cr, qui a permis l'amlioration de l'exponentielle, de certaines constantes, et l'implantation du sinus et du cosinus. Nous exposons l'algorithme pour le cas rationnel, puis nous montrons comment ce cas particulier permet d'obtenir l'exponentielle. Nous utilisons ensuite une mthode similaire pour les autres fonctions. Les expriences montrent que la mthode est plus efficace que celles employes prcdemment dans MPFR.
Diploma Thesis

[1]

Emmanuel Jeandel.
Propriétés structurelles et calculatoires des
pavages.
Habilitation thesis, Université Montpellier 2, 2011.
[ Download ]

[2]

Emmanuel Jeandel.
Techniques algébriques en calcul quantique.
PhD thesis, ENS Lyon, 2005.
[ Download ]
[Show abstract]
Le principal problème étudié est le calcul de l'adhérence de
Zariski de groupes algébriques, et leurs applications en calcul quantique.
On donne ici un algorithme en temps polynomial qui décide si un sousgroupe
finiment engendré d'un groupe reductif est dense dans ce groupe. On
donne également un algorithme qui calcule précisément l'adhérence d'un groupe. Ces résultats sont utilisés afin de résoudre plusieurs problèmes en calcul quantique, en particulier liés aux circuits quantiques. Ainsi divers algorithmes qui décident si des jeux de portes sont universels, ou qui permettent de séparer les différentes notions d'universalité, sont donnés. Nous nous intéressons aussi ici aux automates finis. Nous introduisons ici un nouvel modèle, les automates topologiques, qui permet de généraliser les modèles existants. Nous montrons ainsi, dans un contexte unifié, que tous les modèles d'automates finis classiques, quantiques ou probabilistes ne reconnaissent que des langages rationnels par seuil isolé.

[3]

Emmanuel Jeandel.
Indcidabilit sur les automates quantiques.
Master's thesis, ENS Lyon, 2002.
[ Download ]
[Show abstract]
Aprs avoir introduit les automates quantiques MO et MM, nous
discuterons ici des principaux problmes de dcision qui se posent.
Alors que tous les problmes naturels que l'on peut se poser sont
indcidables pour le modle stochastique, l'existence d'un mot accept avec
seuil strict par un automate quantique MO est montr dcidable, par une mthode
mathmatique base sur quelques proprits
remarquables des groupes de Lie. Tous les autres problmes sont montrs
indcidables par rduction la correspondance de Post, en utilisant un
encodage des mots par des matrices unitaires. Nous dcrirons enfin comment
les diffrents modles rencontrs se simulent entre eux.
Back (Main page)