3 Search Results for "Poupet, Victor"

Document
DOI: 10.4230/LIPIcs.STACS.2023.52
Reconstructing Words Using Queries on Subwords or Factors

Authors: Gwenaël Richomme and Matthieu Rosenfeld

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
We study word reconstruction problems. Improving a previous result by P. Fleischmann, M. Lejeune, F. Manea, D. Nowotka and M. Rigo, we prove that, for any unknown word w of length n over an alphabet of cardinality k, w can be reconstructed from the number of occurrences as subwords (or scattered factors) of O(k²√{nlog₂(n)}) words. Two previous upper bounds obtained by S. S. Skiena and G. Sundaram are also slightly improved: one when considering information on the existence of subwords instead of on the numbers of their occurrences, and, the other when considering information on the existence of factors.
Cite as

Gwenaël Richomme and Matthieu Rosenfeld. Reconstructing Words Using Queries on Subwords or Factors. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{richomme_et_al:LIPIcs.STACS.2023.52,
  author =	{Richomme, Gwena\"{e}l and Rosenfeld, Matthieu},
  title =	{{Reconstructing Words Using Queries on Subwords or Factors}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.52},
  URN =		{urn:nbn:de:0030-drops-177041},
  doi =		{10.4230/LIPIcs.STACS.2023.52},
  annote =	{Keywords: Word reconstruction, Subwords, Factors}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.115
A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods

Authors: Anaël Grandjean and Victor Poupet

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all twodimensional languages recognized by cellular automata working on complete neighborhoods.
Cite as

Anaël Grandjean and Victor Poupet. A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 115:1-115:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.ICALP.2016.115,
  author =	{Grandjean, Ana\"{e}l and Poupet, Victor},
  title =	{{A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{115:1--115:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.115},
  URN =		{urn:nbn:de:0030-drops-62502},
  doi =		{10.4230/LIPIcs.ICALP.2016.115},
  annote =	{Keywords: 2D Cellular automata, linear acceleration, language recognition}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.367
Comparing 1D and 2D Real Time on Cellular Automata

Authors: Anaël Grandjean and Victor Poupet

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood. We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.
Cite as

Anaël Grandjean and Victor Poupet. Comparing 1D and 2D Real Time on Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 367-378, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.STACS.2015.367,
  author =	{Grandjean, Ana\"{e}l and Poupet, Victor},
  title =	{{Comparing 1D and 2D Real Time on Cellular Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{367--378},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.367},
  URN =		{urn:nbn:de:0030-drops-49275},
  doi =		{10.4230/LIPIcs.STACS.2015.367},
  annote =	{Keywords: Cellular automata, real time, language recognition}
}
  • Refine by Author
  • 2 Grandjean, Anaël
  • 2 Poupet, Victor
  • 1 Richomme, Gwenaël
  • 1 Rosenfeld, Matthieu

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 2 language recognition
  • 1 2D Cellular automata
  • 1 Cellular automata
  • 1 Factors
  • 1 Subwords
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2015
  • 1 2016
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact