Document Open Access Logo

Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations

Authors Joel D. Day, Florin Manea, Dirk Nowotka

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.44.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Joel D. Day
  • Loughborough University, UK
  • Kiel University, Germany
Florin Manea
  • Kiel University, Germany
Dirk Nowotka
  • Kiel University, Germany

Funding

Florin Manea’s work was supported by the DFG grant MA 5725/2-1.

Cite As Get BibTex

Joel D. Day, Florin Manea, and Dirk Nowotka. Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.44

Abstract

It is a long standing conjecture that the problem of deciding whether a quadratic word equation has a solution is in NP. It has also been conjectured that the length of a minimal solution to a quadratic equation is at most exponential in the length of the equation, with the latter conjecture implying the former. We show that both conjectures hold for some natural subclasses of quadratic equations, namely the classes of regular-reversed, k-ordered, and variable-sparse quadratic equations. We also discuss a connection of our techniques to the topic of unavoidable patterns, and the possibility of exploiting this connection to produce further similar results.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics on words
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Quadratic Word Equations
  • Length Upper Bounds
  • NP
  • Unavoidable Patterns

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. A. Abdulla, M. F. Atig, Y. Chen, L. Holík, A. Rezine, P. Rümmer, and J. Stenman. Norn: An SMT Solver for String Constraints. In Proc. CAV 2015, volume 9206 of LNCS, pages 462-469, 2015. Google Scholar
  2. A. Aydin, L. Bang, and T. Bultan. Automata-Based Model Counting for String Constraints. In Proc. CAV 2015, volume 9206 of LNCS, pages 255-272, 2015. Google Scholar
  3. C. Barrett, C. L. Conway, M. Deters, L. Hadarean, D. Jovanović, T. King, A. Reynolds, and C. Tinelli. CVC4. In Proc. CAV 2011, volume 6806 of LNCS, pages 171-177, 2011. Google Scholar
  4. M. Berzish, V. Ganesh, and Y. Zheng. Z3str3: A string solver with theory-aware heuristics. In Proc. FMCAD 2017, pages 55-59. IEEE, 2017. Google Scholar
  5. J. D. Day, F. Manea, and D. Nowotka. The Hardness of Solving Simple Word Equations. In Proc. MFCS 2017, volume 83 of LIPIcs, pages 18:1-18:14, 2017. Google Scholar
  6. R. Da̧browski and W. Plandowski. Solving two-variable word equations. In Proc. 31th International Colloquium on Automata, Languages and Programming, ICALP 2004, volume 3142 of Lecture Notes in Computer Science, pages 408-419, 2004. Google Scholar
  7. V. Diekert, A. Jez, and M. Kufleitner. Solutions of Word Equations Over Partially Commutative Structures. In Proc. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 127:1-127:14, 2016. Google Scholar
  8. V. Diekert and J. M. Robson. On Quadratic Word Equations. In Proc. 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999, volume 1563 of Lecture Notes in Computer Science, pages 217-226, 1999. Google Scholar
  9. A. Ehrenfeucht and G. Rozenberg. Finding a Homomorphism Between Two Words is NP-Complete. Information Processing Letters, 9:86-88, 1979. Google Scholar
  10. D. D. Freydenberger. A Logic for Document Spanners. In Proc. 20th International Conference on Database Theory, ICDT 2017, Leibniz International Proceedings in Informatics (LIPIcs), 2017. To appear. Google Scholar
  11. D. D. Freydenberger and M. Holldack. Document Spanners: From Expressive Power to Decision Problems. In Proc. 19th International Conference on Database Theory, ICDT 2016, volume 48 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:17, 2016. Google Scholar
  12. J. Jaffar. Minimal and Complete Word Unification. Journal of the ACM, 37(1):47-85, 1990. Google Scholar
  13. A. Jeż. Recompression: a simple and powerful technique for word equations. In Proc. STACS 2013, volume 20 of LIPIcs, pages 233-244, 2013. Google Scholar
  14. A. Jez. Context Unification is in PSPACE. In Proc. 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014, volume 8573 of Lecture Notes in Computer Science, pages 244-255. Springer, 2014. Google Scholar
  15. A. Jeż. Word Equations in Nondeterministic Linear Space. In Proc. ICALP 2017, volume 80 of LIPIcs, pages 95:1-95:13, 2017. Google Scholar
  16. J. Karhumäki, F. Mignosi, and W. Plandowski. The expressibility of languages and relations by word equations. Journal of the ACM (JACM), 47(3):483-505, 2000. Google Scholar
  17. A. Kiezun, V. Ganesh, P. J. Guo, P. Hooimeijer, and M. D. Ernst. HAMPI: a solver for string constraints. In Proc. ISSTA 2009, pages 105-116. ACM, 2009. Google Scholar
  18. M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Google Scholar
  19. R. C. Lyndon. Equations in free groups. Transactions of the American Mathematical Society, 96:445-457, 1960. Google Scholar
  20. R. C. Lyndon and P. E. Schupp. Combinatorial Group Theory. Springer, 1977. Google Scholar
  21. G. S. Makanin. The problem of solvability of equations in a free semigroup. Sbornik: Mathematics, 32(2):129-198, 1977. Google Scholar
  22. W. Plandowski. Satisfiability of Word Equations with Constants is in NEXPTIME. In Proc. STOC 1999, pages 721-725. ACM, 1999. Google Scholar
  23. W. Plandowski. Satisfiability of word equations with constants is in PSPACE. In Proc. FOCS 1999, pages 495-500. IEEE, 1999. Google Scholar
  24. W. Plandowski and W. Rytter. Application of Lempel-Ziv Encodings to the Solution of Words Equations. In Proc. ICALP 1998, volume 1443 of LNCS, pages 731-742, 1998. Google Scholar
  25. K. U. Schulz. Word Unification and Transformation of Generalized Equations. Journal of Automated Reasoning, 11:149-184, 1995. Google Scholar
  26. A. Thue. Über unendliche Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I Mat. Nat. Kl., 7, 1906. Google Scholar
  27. M. Trinh, D. Chu, and J. Jaffar. Progressive Reasoning over Recursively-Defined Strings. In Proc. CAV 2016, volume 9779 of LNCS, pages 218-240, 2016. Google Scholar
  28. F. Yu, M. Alkhalaf, and T. Bultan. STRANGER: An Automata-based String Analysis Tool for PHP. In Proc. TACAS 2010, volume 6015 of LNCS, 2010. Google Scholar
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 About DROPS Imprint Privacy Contact