Search Results

Documents authored by Saarela, Aleksi

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.140
Hardness Results for Constant-Free Pattern Languages and Word Equations

Authors: Aleksi Saarela

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study constant-free versions of the inclusion problem of pattern languages and the satisfiability problem of word equations. The inclusion problem of pattern languages is known to be undecidable for both erasing and nonerasing pattern languages, but decidable for constant-free erasing pattern languages. We prove that it is undecidable for constant-free nonerasing pattern languages. The satisfiability problem of word equations is known to be in PSPACE and NP-hard. We prove that the nonperiodic satisfiability problem of constant-free word equations is NP-hard. Additionally, we prove a polynomial-time reduction from the satisfiability problem of word equations to the problem of deciding whether a given constant-free equation has a solution morphism α such that α(xy) ≠ α(yx) for given variables x and y.
Cite as

Aleksi Saarela. Hardness Results for Constant-Free Pattern Languages and Word Equations. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 140:1-140:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{saarela:LIPIcs.ICALP.2020.140,
  author =	{Saarela, Aleksi},
  title =	{{Hardness Results for Constant-Free Pattern Languages and Word Equations}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{140:1--140:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.140},
  URN =		{urn:nbn:de:0030-drops-125472},
  doi =		{10.4230/LIPIcs.ICALP.2020.140},
  annote =	{Keywords: Combinatorics on words, pattern language, word equation}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.136
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences

Authors: Dirk Nowotka and Aleksi Saarela

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We solve two long-standing open problems on word equations. Firstly, we prove that a one-variable word equation with constants has either at most three or an infinite number of solutions. The existence of such a bound had been conjectured, and the bound three is optimal. Secondly, we consider independent systems of three-variable word equations without constants. If such a system has a nonperiodic solution, then this system of equations is at most of size 17. Although probably not optimal, this is the first finite bound found. However, the conjecture of that bound being actually two still remains open.
Cite as

Dirk Nowotka and Aleksi Saarela. An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 136:1-136:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nowotka_et_al:LIPIcs.ICALP.2018.136,
  author =	{Nowotka, Dirk and Saarela, Aleksi},
  title =	{{An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{136:1--136:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.136},
  URN =		{urn:nbn:de:0030-drops-91404},
  doi =		{10.4230/LIPIcs.ICALP.2018.136},
  annote =	{Keywords: combinatorics on words, word equations, systems of equations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.55
Word Equations Where a Power Equals a Product of Powers

Authors: Aleksi Saarela

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We solve a long-standing open problem on word equations by proving that if the words x_0, ..., x_n satisfy the equation x_0^k = x_1^k ... x_n^k for three positive values of k, then the words commute. One of our methods is to assign numerical values for the letters, and then study the sums of the letters of words and their prefixes. We also give a geometric interpretation of our methods.
Cite as

Aleksi Saarela. Word Equations Where a Power Equals a Product of Powers. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 55:1-55:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{saarela:LIPIcs.STACS.2017.55,
  author =	{Saarela, Aleksi},
  title =	{{Word Equations Where a Power Equals a Product of Powers}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{55:1--55:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.55},
  URN =		{urn:nbn:de:0030-drops-69793},
  doi =		{10.4230/LIPIcs.STACS.2017.55},
  annote =	{Keywords: Combinatorics on words, Word equations}
}
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