{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:07Z","timestamp":1740109387206,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["389613931 (MA 5725\/2-1)"],"award-info":[{"award-number":["389613931 (MA 5725\/2-1)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For quadratic word equations, there exists an algorithm based on rewriting rules which generates a directed graph describing all solutions to the equation. For regular word equations \u2013 those for which each variable occurs at most once on each side of the equation \u2013 we investigate the properties of this graph, such as bounds on its diameter, size, and DAG-width, as well as providing some insights into symmetries in its structure. As a consequence, we obtain a combinatorial proof that the problem of deciding whether a regular word equation has a solution is in NP.<\/jats:p>","DOI":"10.1007\/s00224-021-10058-5","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T02:02:26Z","timestamp":1635386546000},"page":"662-739","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the structure of solution-sets to regular word equations"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3660-7766","authenticated-orcid":false,"given":"Joel D.","family":"Day","sequence":"first","affiliation":[]},{"given":"Florin","family":"Manea","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"10058_CR1","doi-asserted-by":"crossref","unstructured":"Abdulla, P.A., Atig, M.F., Chen, Y., Hol\u00edk, L., Rezine, A., R\u00fcmmer, P., Stenman, J.: Norn: An SMT Solver for String Constraints. In: Proc. Computer Aided Verification (CAV), Lecture Notes in Computer Science (LNCS), vol. 9206, pp 462\u2013469 (2015)","DOI":"10.1007\/978-3-319-21690-4_29"},{"key":"10058_CR2","unstructured":"Alkhalaf, M., Bultan, T., Yu, F.: STRANGER: an Automata-Based String Analysis Tool for PHP. In: Proc. Tools and Algorithms for the Construction and Analysis of Systems (TACAS), Lecture Notes in Computer Science (LNCS), vol. 6015 (2010)"},{"key":"10058_CR3","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21, 46\u201362 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"10058_CR4","doi-asserted-by":"crossref","unstructured":"Barrett, C., Conway, C.L., Deters, M., Hadarean, L., Jovanovi\u0107, D., King, T., Reynolds, A., Tinelli, C.: CVC4. In: Proc. Computer Aided Verification (CAV), Lecture Notes In Computer Science (LNCS), vol. 6806, pp 171\u2013177 (2011)","DOI":"10.1007\/978-3-642-22110-1_14"},{"issue":"4","key":"10058_CR5","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.jctb.2012.04.004","volume":"102","author":"D Berwanger","year":"2012","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S., Obdrz\u00e1lek, J.: The DAG-width of directed graphs. J Combin Theory Series B 102(4), 900\u2013923 (2012)","journal-title":"J Combin Theory Series B"},{"key":"10058_CR6","doi-asserted-by":"crossref","unstructured":"Berzish, M., Ganesh, V., Zheng, Y.: Z3str3: a String Solver with Theory-Aware Heuristics. In: Proc. Formal Methods in Computer-Aided Design (FMCAD), pp. 55\u201359. IEEE (2017)","DOI":"10.23919\/FMCAD.2017.8102241"},{"key":"10058_CR7","doi-asserted-by":"crossref","unstructured":"Day, J.D., Ganesh, V., He, P., Manea, F., Nowotka, D.: The Satisfiability of Word Equations: Decidable and Undecidable Theories. In: Potapov, I., Reynier, P. (eds.) Proc. 12th International Conference on Reachability Problems, RP 2018, Lecture Notes in Computer Science (LNCS), vol. 11123, pp 15\u201329 (2018)","DOI":"10.1007\/978-3-030-00250-3_2"},{"key":"10058_CR8","unstructured":"Day, J.D., Manea, F., Nowotka, D.: The Hardness of Solving Simple Word Equations. In: Proc. Mathematical Foundations of Computer Science (MFCS), LIPIcs, vol. 83, pp 18:1\u201318:14 (2017)"},{"key":"10058_CR9","unstructured":"Day, J.D., Manea, F., Nowotka, D.: Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations. In: Proc. Mathematical Foundations of Computer Science (MFCS), LIPIcs, vol. 138, pp 44:1\u201344:15 (2019)"},{"key":"10058_CR10","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/j.ic.2016.09.009","volume":"251","author":"V Diekert","year":"2016","unstructured":"Diekert, V., Je\u017c, A., Plandowski, W.: Finding all solutions of equations in free groups and monoids with involution. Inf. Comput. 251, 263\u2013286 (2016)","journal-title":"Inf. Comput."},{"key":"10058_CR11","doi-asserted-by":"crossref","unstructured":"Diekert, V., Robson, J.M.: On Quadratic Word Equations. In: Proc. 16Th Annual Symposium on Theoretical Aspects of Computer Science, STACS, Lecture Notes in Computer Science (LNCS), vol. 1563, pp 217\u2013226 (1999)","DOI":"10.1007\/3-540-49116-3_20"},{"key":"10058_CR12","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0020-0190(79)90135-2","volume":"9","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Rozenberg, G.: Finding a homomorphism between two words is NP-complete. Inf. Process. Lett. 9, 86\u201388 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"7","key":"10058_CR13","doi-asserted-by":"publisher","first-page":"1679","DOI":"10.1007\/s00224-018-9874-1","volume":"63","author":"DD Freydenberger","year":"2019","unstructured":"Freydenberger, D.D.: A logic for document spanners. Theory of Computing Systems 63(7), 1679\u20131754 (2019)","journal-title":"Theory of Computing Systems"},{"issue":"4","key":"10058_CR14","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1007\/s00224-017-9770-0","volume":"62","author":"DD Freydenberger","year":"2018","unstructured":"Freydenberger, D.D., Holldack, M.: Document spanners: From expressive power to decision problems. Theory of Computing Systems 62(4), 854\u2013898 (2018)","journal-title":"Theory of Computing Systems"},{"key":"10058_CR15","doi-asserted-by":"crossref","unstructured":"Je\u017c, A.: Recompression: a simple and powerful technique for word equations. J. ACM 63 (2016)","DOI":"10.1145\/2743014"},{"key":"10058_CR16","unstructured":"Je\u017c, A.: Word Equations in Nondeterministic Linear Space. In: Proc. International Colloquium on Automata, Languages and Programming (ICALP), LIPIcs, vol. 80, pp 95:1\u201395:13 (2017)"},{"key":"10058_CR17","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/337244.337255","volume":"47","author":"J Karhum\u00e4ki","year":"2000","unstructured":"Karhum\u00e4ki, J., Mignosi, F., Plandowski, W.: The expressibility of languages and relations by word equations. J. ACM 47, 483\u2013505 (2000)","journal-title":"J. ACM"},{"key":"10058_CR18","doi-asserted-by":"crossref","unstructured":"Kiezun, A., Ganesh, V., Guo, P.J., Hooimeijer, P., Ernst, M.D.: HAMPI: a Solver for String Constraints. In: Proc. ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA), pp 105\u2013116. ACM (2009)","DOI":"10.1145\/1572272.1572286"},{"key":"10058_CR19","doi-asserted-by":"crossref","unstructured":"Lin, A.W., Barcel\u00f3, P.: String Solving with Word Equations and Transducers: Towards a Logic for Analysing Mutation Xss. In: ACM SIGPLAN Notices, vol. 51, pp 123\u2013136. ACM (2016)","DOI":"10.1145\/2914770.2837641"},{"key":"10058_CR20","doi-asserted-by":"crossref","unstructured":"Lin, A.W., Majumdar, R.: Quadratic Word Equations with Length Constraints, Counter Systems, and Presburger Arithmetic with Divisibility. In: Lahiri, S.K., Wang, C. (eds.) Proc. 16th International Symposium on Automated Technology for Verification and Analysis (ATVA), Lecture Notes in Computer Science (LNCS), vol. 11138, pp 352\u2013369. Springer (2018)","DOI":"10.1007\/978-3-030-01090-4_21"},{"key":"10058_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, New York (2002)"},{"issue":"2","key":"10058_CR22","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1070\/SM1977v032n02ABEH002376","volume":"32","author":"GS Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Sbornik: Mathematics 32(2), 129\u2013198 (1977)","journal-title":"Sbornik: Mathematics"},{"issue":"5","key":"10058_CR23","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1142\/S0129054118420108","volume":"29","author":"F Manea","year":"2018","unstructured":"Manea, F., Nowotka, D., Schmid, M.L.: On the complexity of solving restricted word equations. Int. J. Found. Comput. Sci. 29(5), 893\u2013909 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10058_CR24","doi-asserted-by":"crossref","unstructured":"Petre, E.: An Elementary Proof for the Non-Parametrizability of the Equation Xyz = Zvx. In: Proc. 29Th International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science (LNCS), vol. 3153, pp 807\u2013817 (2004)","DOI":"10.1007\/978-3-540-28629-5_63"},{"key":"10058_CR25","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Satisfiability of Word Equations with Constants is in PSPACE. In: Proc. Foundations of Computer Science (FOCS), pp. 495\u2013500. IEEE (1999)","DOI":"10.1109\/SFFCS.1999.814622"},{"key":"10058_CR26","doi-asserted-by":"crossref","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel-Ziv Encodings to the Solution of Words Equations. In: Proc. International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science (LNCS), vol. 1443, pp 731\u2013742 (1998)","DOI":"10.1007\/BFb0055097"},{"key":"10058_CR27","doi-asserted-by":"crossref","unstructured":"Schulz, K.U.: Makanin\u2019s Algorithm for Word Equations-Two Improvements and a Generalization. In: International Workshop on Word Equations and Related Topics, pp. 85\u2013150. Springer (1990)","DOI":"10.1007\/3-540-55124-7_4"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10058-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10058-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10058-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T22:34:51Z","timestamp":1726007691000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10058-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10058"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10058-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"4 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}