2 Search Results for "Rajasekaran, Aayush"

Document
DOI: 10.4230/LIPIcs.MFCS.2018.18
Lagrange's Theorem for Binary Squares

Authors: P. Madhusudan, Dirk Nowotka, Aayush Rajasekaran, and Jeffrey Shallit

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We show how to prove theorems in additive number theory using a decision procedure based on finite automata. Among other things, we obtain the following analogue of Lagrange's theorem: every natural number > 686 is the sum of at most 4 natural numbers whose canonical base-2 representation is a binary square, that is, a string of the form xx for some block of bits x. Here the number 4 is optimal. While we cannot embed this theorem itself in a decidable theory, we show that stronger lemmas that imply the theorem can be embedded in decidable theories, and show how automated methods can be used to search for these stronger lemmas.
Cite as

P. Madhusudan, Dirk Nowotka, Aayush Rajasekaran, and Jeffrey Shallit. Lagrange's Theorem for Binary Squares. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{madhusudan_et_al:LIPIcs.MFCS.2018.18,
  author =	{Madhusudan, P. and Nowotka, Dirk and Rajasekaran, Aayush and Shallit, Jeffrey},
  title =	{{Lagrange's Theorem for Binary Squares}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.18},
  URN =		{urn:nbn:de:0030-drops-96003},
  doi =		{10.4230/LIPIcs.MFCS.2018.18},
  annote =	{Keywords: binary square, theorem-proving, finite automaton, decision procedure, decidable theory, additive number theory}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.54
Sums of Palindromes: an Approach via Automata

Authors: Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Recently, Cilleruelo, Luca, & Baxter proved, for all bases b >= 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome. However, the cases b = 2, 3, 4 were left unresolved. We prove, using a decision procedure based on automata, that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem.
Cite as

Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith. Sums of Palindromes: an Approach via Automata. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 54:1-54:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{rajasekaran_et_al:LIPIcs.STACS.2018.54,
  author =	{Rajasekaran, Aayush and Shallit, Jeffrey and Smith, Tim},
  title =	{{Sums of Palindromes: an Approach via Automata}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{54:1--54:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.54},
  URN =		{urn:nbn:de:0030-drops-84976},
  doi =		{10.4230/LIPIcs.STACS.2018.54},
  annote =	{Keywords: finite automaton, nested-word automaton, decision procedure, palindrome, additive number theory}
}
  • Refine by Author
  • 2 Rajasekaran, Aayush
  • 2 Shallit, Jeffrey
  • 1 Madhusudan, P.
  • 1 Nowotka, Dirk
  • 1 Smith, Tim

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Constructive mathematics
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 2 additive number theory
  • 2 decision procedure
  • 2 finite automaton
  • 1 binary square
  • 1 decidable theory
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2018

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