{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:05:33Z","timestamp":1740096333483,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392115"},{"type":"electronic","value":"9783642392122"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39212-2_30","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T09:09:19Z","timestamp":1372756159000},"page":"324-335","source":"Crossref","is-referenced-by-count":2,"title":["One-Variable Word Equations in Linear Time"],"prefix":"10.1007","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"30_CR1","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O. Berkman","year":"1993","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput.\u00a022(2), 221\u2013242 (1993)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"30_CR2","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s00453-009-9375-3","volume":"60","author":"R. D\u0105browski","year":"2011","unstructured":"D\u0105browski, R., Plandowski, W.: On word equations in one variable. Algorithmica\u00a060(4), 819\u2013828 (2011)","journal-title":"Algorithmica"},{"key":"30_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-642-31594-7_45","volume-title":"Automata, Languages, and Programming","author":"A. Je\u017c","year":"2012","unstructured":"Je\u017c, A.: Faster fully compressed pattern matching by recompression. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 533\u2013544. Springer, Heidelberg (2012)"},{"key":"30_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-642-38905-4_17","volume-title":"CPM","author":"A. Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Approximation of grammar-based compression via recompression. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol.\u00a07922, pp. 165\u2013176. Springer, Heidelberg (2013)"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Je\u017c, A.: The complexity of compressed membership problems for finite automata. Theory of Computing Systems, 1\u201334 (2013), \n                    \n                      http:\/\/dx.doi.org\/10.1007\/s00224-013-9443-6","DOI":"10.1007\/s00224-013-9443-6"},{"key":"30_CR6","series-title":"LIPIcs","first-page":"233","volume-title":"STACS","author":"A. Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Recompression: a simple and powerful technique for word equations. In: Portier, N., Wilke, T. (eds.) STACS. LIPIcs, vol.\u00a020, pp. 233\u2013244. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2013), \n                    \n                      http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2013\/3937"},{"issue":"6","key":"30_CR7","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J. K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM\u00a053(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T. Kasai","year":"2001","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 181\u2013192. Springer, Heidelberg (2001)"},{"issue":"2","key":"30_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1142\/S0129054111008088","volume":"22","author":"M. Laine","year":"2011","unstructured":"Laine, M., Plandowski, W.: Word equations with one unknown. Int. J. Found. Comput. Sci.\u00a022(2), 345\u2013375 (2011)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-20712-9_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Lohrey","year":"2011","unstructured":"Lohrey, M., Mathissen, C.: Compressed membership in automata with compressed labels. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 275\u2013288. Springer, Heidelberg (2011)"},{"issue":"103","key":"30_CR11","first-page":"147","volume":"2","author":"G.S. Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Matematicheskii Sbornik\u00a02(103), 147\u2013236 (1977) (in Russian)","journal-title":"Matematicheskii Sbornik"},{"issue":"2","key":"30_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02522825","volume":"17","author":"K. Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica\u00a017(2), 183\u2013198 (1997)","journal-title":"Algorithmica"},{"key":"30_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/3-540-58338-6_80","volume-title":"Mathematical Foundations of Computer Science 1994","author":"S.E. Obono","year":"1994","unstructured":"Obono, S.E., Goralcik, P., Maksimenko, M.N.: Efficient solving of the word equations in one variable. In: Privara, I., Ru\u017ei\u010dka, P., Rovan, B. (eds.) MFCS 1994. LNCS, vol.\u00a0841, pp. 336\u2013341. Springer, Heidelberg (1994)"},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in NEXPTIME. In: STOC, pp. 721\u2013725 (1999)","DOI":"10.1145\/301250.301443"},{"issue":"3","key":"30_CR15","first-page":"483","volume":"51","author":"W. Plandowski","year":"2004","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. J.\u00a0ACM\u00a051(3), 483\u2013496 (2004)","journal-title":"J.\u00a0ACM"},{"key":"30_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/BFb0055097","volume-title":"Automata, Languages and Programming","author":"W. Plandowski","year":"1998","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel-Ziv encodings to the solution of word equations. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 731\u2013742. Springer, Heidelberg (1998)"},{"issue":"2-4","key":"30_CR17","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1016\/j.jda.2004.08.016","volume":"3","author":"H. Sakamoto","year":"2005","unstructured":"Sakamoto, H.: A fully linear-time approximation algorithm for grammar-based compression. J. Discrete Algorithms\u00a03(2-4), 416\u2013430 (2005)","journal-title":"J. Discrete Algorithms"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39212-2_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:04:16Z","timestamp":1557896656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39212-2_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392115","9783642392122"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39212-2_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}