papers.bib

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

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

@article{siam,
  author = {Vincent D. Blondel and Emmanuel Jeandel and Pascal Koiran and Natacha Portier},
  title = {{Decidable and Undecidable Problems about Quantum Automata}},
  journal = {SIAM Journal on Computing},
  year = {2005},
  volume = {34},
  number = {6},
  pages = {1464--1473},
  doi = {10.1137/S0097539703425861},
  abstract = {We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.},
  keywords = {Quantum Automata, Probabilistic Automata, Undecidability, Algebraic Groups, Algebraic Geometry.},
  rr = {#RR2003-24},
  core = {A$^\star$}
}

@article{qagr,
  author = {Harm Derksen and Emmanuel Jeandel and Pascal Koiran},
  title = {{Quantum automata and algebraic groups}},
  journal = {Journal of Symbolic Computation},
  year = {2005},
  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.},
  keywords = {Quantum automata, Algebraic groups, Algebraic geometry},
  volume = {39},
  number = {3--4},
  pages = {357--371},
  month = mar # {--} # apr,
  doi = {10.1016/j.jsc.2004.11.008},
  elsevier = {http://authors.elsevier.com/sd/article/S0747717105000088},
  rr = {#RR2003-39},
  core = {A}
}

@article{vectors,
  author = { Pierre Charbit and Emmanuel Jeandel and Pascal Koiran and  Sylvain Perifel and St\'ephan Thomass\'e},
  title = {{Finding a Vector Orthogonal to Roughly Half a Collection of Vectors.}},
  journal = {Journal of Complexity},
  year = {2008},
  abstract = {Dimitri Grigoriev has shown that for any family of $N$ vectors
  in the $d$-dimensional 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-\sqrt{N}/2,N/2+\sqrt{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.},
  keywords = {Algebraic complexity, decision trees, parallel algorithms, derandomization},
  volume = {24},
  number = {1},
  pages = {39--53},
  doi = {10.1016/j.jco.2006.09.005},
  month = feb,
  rr = {#RR2006-05},
  core = {A}
}

@article{topauto,
  author = {Emmanuel Jeandel},
  title = {{Topological Automata}},
  journal = {Theory of Computing Systems},
  year = {2007},
  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},
  volume = {40},
  number = {4},
  pages = {397--407},
  month = jun,
  doi = {10.1007/s00224-006-1314-y},
  preliminary = {PUB/stacs2005-prel.ps.gz},
  core = {C}
}

@article{Commuting,
  author = {Emmanuel Jeandel and Nicolas Ollinger},
  title = {{Playing with Conway's Problem}},
  journal = {Theoretical Computer Science},
  year = 2008,
  doi = {10.1016/j.tcs.2008.09.026},
  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 co-recursively 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.},
  keywords = {Conway's problem;commutation;centralizer;game theory},
  rr = {#CCSD-00013788},
  volume = 409,
  pages = {557--564},
  core = {A}
}

@article{UnPerio,
  author = {Emmanuel Jeandel},
  title = {{The periodic domino problem revisited}},
  year = 2010,
  journal = {Theoretical Computer Science},
  doi = {10.1016/j.tcs.2010.08.017},
  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.},
  volume = 411,
  pages = {4010--4016},
  core = {A}
}