{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:48:53Z","timestamp":1724449733079},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,8]]},"abstract":"<jats:p> We investigate the complexity of the solvability problem for restricted classes of word equations with and without regular constraints. The solvability problem for unrestricted word equations remains [Formula: see text]-hard, even if, on both sides, between any two occurrences of the same variable no other different variable occurs; for word equations with regular constraints, the solvability problems remains [Formula: see text]-hard for equations whose two sides share no variables or with two variables, only one of which is repeated. On the other hand, word equations with only one repeated variable (but an arbitrary number of variables) and at least one non-repeated variable on each side, can be solved in polynomial-time. <\/jats:p>","DOI":"10.1142\/s0129054118420108","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T06:47:08Z","timestamp":1534834028000},"page":"893-909","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Solving Restricted Word Equations"],"prefix":"10.1142","volume":"29","author":[{"given":"Florin","family":"Manea","sequence":"first","affiliation":[{"name":"Department of Computer Science, Kiel University, D-24098 Kiel, Germany"}]},{"given":"Dirk","family":"Nowotka","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Kiel University, D-24098 Kiel, Germany"}]},{"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[{"name":"Trier University, Fachbereich IV \u2013 Abteilung Informatikwissenschaften, D-54286 Trier, Germany"}]}],"member":"219","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"S0129054118420108BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"S0129054118420108BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9375-3"},{"key":"S0129054118420108BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.03.006"},{"key":"S0129054118420108BIB006","author":"Fernau H.","year":"2015","journal-title":"Theory of Computing Systems"},{"key":"S0129054118420108BIB007","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"S0129054118420108BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9931-3"},{"key":"S0129054118420108BIB009","doi-asserted-by":"publisher","DOI":"10.1145\/2743014"},{"key":"S0129054118420108BIB011","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019"},{"key":"S0129054118420108BIB012","first-page":"147","volume":"103","author":"Makanin G.","year":"1977","journal-title":"Matematicheskii Sbornik"},{"key":"S0129054118420108BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.08.010"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118420108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T08:58:35Z","timestamp":1565168315000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118420108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":10,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2018,8,21]]},"published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.1142\/S0129054118420108"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118420108","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}