{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T18:28:45Z","timestamp":1648837725392},"reference-count":17,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>Membership problems for compressed strings in regular languages are investigated. Strings are represented by straight-line programs, i.e., context-free grammars that generate exactly one string. For the representation of regular languages, various formalisms with different degrees of succinctness (e.g., suitably extended regular expressions, hierarchical automata) are considered. Precise complexity bounds are derived. Among other results, it is shown that the compressed membership problem for regular expressions with intersection is PSPACE-complete. This solves an open problem of Plandowski and Rytter.<\/jats:p>","DOI":"10.1142\/s012905411000757x","type":"journal-article","created":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T09:40:06Z","timestamp":1286271606000},"page":"817-841","source":"Crossref","is-referenced-by-count":3,"title":["COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA"],"prefix":"10.1142","volume":"21","author":[{"given":"MARKUS","family":"LOHREY","sequence":"first","affiliation":[{"name":"Universit\u00e4t Leipzig, Institut f\u00fcr Informatik, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1145\/503502.503503"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00271645"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"rf5","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2013completeness","author":"Garey M. R.","year":"1979"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9054-1"},{"key":"rf7","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"Greenlaw R.","year":"1995"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00064-X"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00017-7"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(05)80006-7"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445950"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.002"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1098"},{"key":"rf19","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60207-8_23"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90018-7"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411000757X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T03:33:14Z","timestamp":1636601594000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411000757X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":17,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1142\/S012905411000757X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411000757x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10]]}}}