Search Results

Documents authored by Idziaszek, Tomasz

Document
DOI: 10.4230/LIPIcs.FUN.2021.16
Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation

Authors: Tomasz Idziaszek

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
In the Zeckendorf representation an integer is expressed as a sum of Fibonacci numbers in which no two are consecutive. We show O(n log n) algorithm for multiplication of two n-digit numbers in Zeckendorf representation. For this purpose we investigate a relationship between the numeral system using Zeckendorf representations and the golden ratio numeral system. We also show O(n) algorithms for converting numbers between these systems.
Cite as

Tomasz Idziaszek. Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 16:1-16:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{idziaszek:LIPIcs.FUN.2021.16,
  author =	{Idziaszek, Tomasz},
  title =	{{Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{16:1--16:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.16},
  URN =		{urn:nbn:de:0030-drops-127770},
  doi =		{10.4230/LIPIcs.FUN.2021.16},
  annote =	{Keywords: Fibonacci numbers, Zeckendorf representation, multiplication algorithm, Fast Fourier Transform, golden ratio numeral system, Lucas numbers}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.562
Regular languages of thin trees

Authors: Mikolaj Bojanczyk, Tomasz Idziaszek, and Michal Skrzypczak

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
An infinite tree is called thin if it contains only countably many infinite branches. Thin trees can be seen as intermediate structures between infinite words and infinite trees. In this work we investigate properties of regular languages of thin trees. Our main tool is an algebra suitable for thin trees. Using this framework we characterize various classes of regular languages: commutative, open in the standard topology, closed under two variants of bisimulational equivalence, and definable in WMSO logic among all trees. We also show that in various meanings thin trees are not as rich as all infinite trees. In particular we observe a parity index collapse to level (1,3) and a topological complexity collapse to co-analytic sets. Moreover, a gap property is shown: a regular language of thin trees is either WMSO-definable among all trees or co-analytic-complete.
Cite as

Mikolaj Bojanczyk, Tomasz Idziaszek, and Michal Skrzypczak. Regular languages of thin trees. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 562-573, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.STACS.2013.562,
  author =	{Bojanczyk, Mikolaj and Idziaszek, Tomasz and Skrzypczak, Michal},
  title =	{{Regular languages of thin trees}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{562--573},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.562},
  URN =		{urn:nbn:de:0030-drops-39655},
  doi =		{10.4230/LIPIcs.STACS.2013.562},
  annote =	{Keywords: infinite trees, regular languages, effective characterizations, topological complexity}
}
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