{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T09:02:09Z","timestamp":1648890129221},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2015,2]]},"abstract":"<jats:p> The paper is a part of an ongoing program which aims to show that the problem of satisfiability of a system of equations in a free group (hyperbolic or even toral relatively hyperbolic group) is NP-complete. For that, we study compression of solutions with straight-line programs (SLPs) as suggested originally by Plandowski and Rytter in the context of a single word equation. We review some basic results on SLPs and give full proofs in order to keep this fundamental part of the program self-contained. Next we study systems of equations with constraints in free groups and more generally in free products of abelian groups. We show how to compress minimal solutions with extended Parikh-constraints. This type of constraints allows to express semi-linear conditions as e.g. alphabetic information. The result relies on some combinatorial analysis and has not been shown elsewhere. We show similar compression results for Boolean formula of equations over a torsion-free \u03b4-hyperbolic group. The situation is much more delicate than in free groups. As byproduct we improve the estimation of the \"capacity\" constant used by Rips and Sela in their paper \"Canonical representatives and equations in hyperbolic groups\" from a double-exponential bound in \u03b4 to some single-exponential bound. The final section shows compression results for toral relatively hyperbolic groups using the work of Dahmani: We show that given a system of equations over a fixed toral relatively hyperbolic group, for every solution of length N there is an SLP for another solution such that the size of the SLP is bounded by some polynomial p(s + log N) where s is the size of the system. <\/jats:p>","DOI":"10.1142\/s0218196715400056","type":"journal-article","created":{"date-parts":[[2015,1,9]],"date-time":"2015-01-09T08:33:15Z","timestamp":1420792395000},"page":"81-111","source":"Crossref","is-referenced-by-count":0,"title":["SLP compression for solutions of equations with constraints in free and hyperbolic groups"],"prefix":"10.1142","volume":"25","author":[{"given":"Volker","family":"Diekert","sequence":"first","affiliation":[{"name":"Formale Methoden der Informatik (FMI), Universit\u00e4t Stuttgart, Universit\u00e4tsstra\u00dfe 38, 70569 Stuttgart, Germany"}]},{"given":"Olga","family":"Kharlampovich","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Hunter College and Graduate Center, CUNY, 695 Park Ave, New York, 10065, USA"}]},{"given":"Atefeh Mohajeri","family":"Moghaddam","sequence":"additional","affiliation":[{"name":"Department Mathematics and Statistics, McGill University, Montreal, Canada, H3A 0B9, Canada"}]}],"member":"219","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"key":"rf2","series-title":"Lecture Notes in Mathematics","volume-title":"G\u00e9om\u00e9trie et Th\u00e9orie des Groupes: Les Groupes Hyperboliques de M. Gromov","volume":"1441","author":"Coornaert M.","year":"1991"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771780"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-009-0084-z"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1112\/jtopol\/jtq010"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.04.002"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38771-5_2"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9153-7"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445950"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0016"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522825"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01241140"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.4171\/CMH\/142"},{"key":"rf27","doi-asserted-by":"crossref","unstructured":"K. U.\u00a0Schulz, Word Equations and Related Topics, Lecture Notes in Computer Science\u00a0572, ed. K. U.\u00a0Schulz (Springer-Verlag, Heidelberg, 1991)\u00a0pp. 85\u2013150.","DOI":"10.1007\/3-540-55124-7_4"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196715400056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:26:38Z","timestamp":1565137598000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196715400056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2]]},"references-count":15,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2015,3,25]]},"published-print":{"date-parts":[[2015,2]]}},"alternative-id":["10.1142\/S0218196715400056"],"URL":"https:\/\/doi.org\/10.1142\/s0218196715400056","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2]]}}}