{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:57Z","timestamp":1759638417877},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,11]]},"abstract":"<jats:p> The language [Formula: see text] consists of first halfs of strings in L. Many other variants of a proportional removal operation have been considered in the literature and a characterization of removal operations that preserve regularity is known. We consider the nondeterministic state complexity of the operation [Formula: see text] and, more generally, of polynomial removals as defined by Domaratzki (J. Automata, Languages and Combinatorics 7(4), 2002). We give an O(n<jats:sup>2<\/jats:sup>) upper bound for the nondeterministic state complexity of polynomial removals and a matching lower bound in cases where the polynomial is a sum of a monomial and a constant, or when the polynomial has rational roots. <\/jats:p>","DOI":"10.1142\/s0129054114400103","type":"journal-article","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T03:48:03Z","timestamp":1421207283000},"page":"823-835","source":"Crossref","is-referenced-by-count":2,"title":["NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS"],"prefix":"10.1142","volume":"25","author":[{"given":"DANIEL","family":"GO\u010c","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada"}]},{"given":"ALEXANDROS","family":"PALIOUDAKIS","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u02bcs University, Kingston, Ontario K7L 3N6, Canada"}]},{"given":"KAI","family":"SALOMAA","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u02bcs University, Kingston, Ontario K7L 3N6, Canada"}]}],"member":"219","published-online":{"date-parts":[[2015,1,14]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90142-8"},{"issue":"4","key":"p_3","first-page":"455","volume":"7","author":"Domaratzki M.","year":"2002","journal-title":"Languages and Combinatorics"},{"issue":"2","key":"p_5","first-page":"193","volume":"8","author":"Goldstine J.","year":"2002","journal-title":"J. UCS"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1112\/S002557930000838X"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002199"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054109006747"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.013"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1137\/0222067"},{"key":"p_11","first-page":"328","volume":"9","author":"Lupanov O.","year":"1963","journal-title":"Problemy Kibernetiki"},{"issue":"5","key":"p_12","first-page":"1373","volume":"11","author":"Maslov A.","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223108"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90030-X"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:36:34Z","timestamp":1565116594000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11]]},"references-count":14,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2015,1,14]]},"published-print":{"date-parts":[[2014,11]]}},"alternative-id":["10.1142\/S0129054114400103"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400103","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11]]}}}