proc.bib

@comment{{This file has been generated by bib2bib 1.95}}

@comment{{Command line: bib2bib -c $type="INPROCEEDINGS" ../CV/publis.bib -ob proc.bib}}

@inproceedings{jeandelicalp2004,
  author = {Emmanuel Jeandel},
  title = {{Universality in Quantum Computation}},
  volume = {3142},
  series = {Lecture Notes in Computer Science},
  booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)},
  year = {2004},
  publisher = {Springer},
  pages = {793--804},
  doi = {10.1007/978-3-540-27836-8_67},
  preliminary = {PUB/icalp2004-prel.ps.gz},
  directdownload = {publis/icalp2004-prel.ps.gz},
  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."},
  keywords = {Quantum circuits, Universality, Algebraic Geometry},
  core = {A}
}

@inproceedings{jeandelstacs2005,
  author = {Emmanuel Jeandel},
  title = {{Topological Automata}},
  volume = {3404},
  series = {Lecture Notes in Computer Science},
  booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)},
  year = {2005},
  pages = {389--398},
  publisher = {Springer},
  doi = {10.1007/978-3-540-31856-9_32},
  preliminary = {PUB/stacs2005-prel.ps.gz},
  directdownload = {publis/stacs2005-prel.ps.gz},
  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 non-deterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.},
  keywords = {Finite Automata, Formal Languages, Probabilistic Automata,
  Quantum Automata},
  core = {B}
}

@inproceedings{ballierstacs2008,
  author = {Alexis Ballier and Bruno Durand and Emmanuel Jeandel},
  title = {{Structural Aspects of Tilings}},
  booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)},
  year = {2008},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  doi = {10.4230/LIPIcs.STACS.2008.1334},
  pages = {61--72},
  download = {http://drops.dagstuhl.de/opus/volltexte/2008/1334/},
  abstract = {    In this paper, we study the structure of
    the set of tilings produced by any given tile-set. 
    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 Cantor-Bendixson rank.
    Our first main result is that a tile-set 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.},
  keywords = {Tilings, Domino, Patterns, Tiling Preorder, Tiling Structure},
  core = {B}
}

@inproceedings{ballier2008,
  author = {Alexis Ballier and Emmanuel Jeandel},
  title = {{Tilings and Model Theory}},
  booktitle = {Symposium on Cellular Automata Journ{\'e}es Automates Cellulaires (JAC)},
  address = {Moscow},
  publisher = {MCCME Publishing House},
  year = 2008,
  pages = {29--39},
  hal = {hal.archives-ouvertes.fr/hal-00273698_v1},
  download = {http://hal.archives-ouvertes.fr/hal-00273698/en/},
  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.},
  keywords = {Tilings, Domino, Patterns, Model Theory},
  core = {C}
}

@inproceedings{jeandeltheyssier,
  author = {Emmanuel Jeandel and Guillaume Theyssier},
  title = {{Subshifts, Languages and Logic}},
  volume = {5583},
  series = {Lecture Notes in Computer Science},
  pages = {288--299},
  booktitle = {Developments in Language Theory (DLT)},
  year = {2009},
  publisher = {Springer},
  doi = {10.1007/978-3-642-02737-6_23},
  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).},
  preliminary = {http://hal.archives-ouvertes.fr/hal-00375816/en/},
  core = {B}
}

@inproceedings{EJLatin,
  author = {Alexis Ballier and Bruno Durand and Emmanuel Jeandel},
  title = {Tilings robust to errors},
  volume = {6034},
  series = {Lecture Notes in Computer Science},
  pages = {480--491},
  booktitle = {Latin American Theoretical Informatics Symposium (LATIN)},
  year = {2010},
  doi = {10.1007/978-3-642-12200-2_42},
  publisher = {Springer},
  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 error-free 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.},
  preliminary = {PUB/robust.pdf},
  core = {B}
}

@inproceedings{PVEJDLT,
  author = {Emmanuel Jeandel and Pascal Vanier},
  title = {{Periodicity in Tilings}},
  booktitle = {Developments in Language Theory (DLT)},
  volume = {6224},
  series = {Lecture Notes in Computer Science},
  year = {2010},
  pages = {243--254},
  core = {B},
  doi = {10.1007/978-3-642-14455-4_23},
  publisher = {Springer},
  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.},
  preliminary = {http://arxiv.org/abs/0909.3997}
}

@inproceedings{ballier2010,
  author = {Alexis Ballier and Emmanuel Jeandel},
  title = {{Computing (or not) quasi-periodicity functions of tilings}},
  booktitle = {Symposium on Cellular Automata (JAC)},
  year = {2010},
  pages = {54--64},
  abstract = {We know that tilesets that can tile the plane always admit a quasi-periodic
tiling, yet they hold many uncomputable
properties.
The quasi-periodicity function is one way to measure the regularity of a
quasi-periodic tiling.
We prove that the tilings by a tileset that admits only quasi-periodic tilings
have a recursively (and uniformly) bounded quasi-periodicity function.
This corrects an error from [CervelleDurand2004] which stated the
contrary.
Instead we construct a tileset for which any quasi-periodic tiling has a
quasi-periodicity function that cannot be recursively bounded.
We provide such a construction for $1-$dimensional effective subshifts and
obtain as a corollary the result for tilings of the plane via recent
links between these objects.},
  core = {C},
  download = {http://hal.archives-ouvertes.fr/hal-00542498/en/},
  hal = {hal.archives-ouvertes.fr/hal-00542498}
}

@inproceedings{vanier2010,
  author = {Emmanuel Jeandel and Pascal Vanier},
  title = {Slopes of tilings},
  booktitle = {Symposium on Cellular Automata (JAC)},
  year = {2010},
  pages = {145--155},
  abstract = {We study here slopes of periodicity of tilings.
A tiling is of slope $\theta$ if it is periodic along direction
$\theta$ 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.
},
  download = {http://hal.archives-ouvertes.fr/hal-00542000/en/},
  hal = {hal.archives-ouvertes.fr/hal-00542000},
  core = {C}
}

@inproceedings{vanier2011,
  author = {Emmanuel Jeandel and Pascal Vanier},
  title = {{$\Pi_1^0$ sets and tilings}},
  pages = {230--239},
  booktitle = {Theory and Applications of Models of Computation (TAMC)},
  year = {2011},
  volume = {6648},
  series = {Lecture Notes in Computer Science},
  abstract = {In this paper, we prove that given any $\Pi_1^0$ subset
  $P$ of $\{0,1\}^\NN$  there is a tileset $\tau$ with a set of configurations
  $C$ such that $P \times \ZZ^2$ is recursively homeomorphic to $C\setminus U$ 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.},
  doi = {10.1007/978-3-642-20877-5_24},
  core = {B},
  preliminary = {http://arxiv.org/abs/1102.1189}
}