{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T11:46:14Z","timestamp":1651837574724},"reference-count":31,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:p> Partially lossy queue monoids (plq monoids) model the behavior of queues that can non-deterministically forget specified parts of their content at any time. We call the subsets of this monoid partially lossy queue languages (plq languages). While many decision problems on recognizable plq languages are decidable, most of them are undecidable if the languages are rational. In particular, in this monoid the classes of rational and recognizable languages do not coincide. This is due to the fact that the class of recognizable plq languages is not closed under multiplication and iteration. However, we can generate the recognizable plq languages using special rational expressions consisting of the Boolean operations and restricted versions of multiplication and iteration. From these special rational expressions we can also obtain an MSO logic describing the recognizable plq languages. Moreover, we provide similar results for the class of aperiodic languages in the plq monoid. <\/jats:p>","DOI":"10.1142\/s0218196722500230","type":"journal-article","created":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T01:26:16Z","timestamp":1645752376000},"page":"483-528","source":"Crossref","is-referenced-by-count":0,"title":["Rational, recognizable, and aperiodic partially lossy queue languages"],"prefix":"10.1142","volume":"32","author":[{"given":"Chris","family":"K\u00f6cher","sequence":"first","affiliation":[{"name":"Automata and Logics Group, Technische Universit\u00e4t Ilmenau, P. O. Box 10 05 65, 98684 Ilmenau, Germany"}]}],"member":"219","published-online":{"date-parts":[[2022,2,24]]},"reference":[{"key":"S0218196722500230BIB001","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0053"},{"key":"S0218196722500230BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"S0218196722500230BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/322374.322380"},{"key":"S0218196722500230BIB004","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S0218196722500230BIB005","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0003"},{"key":"S0218196722500230BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0016249"},{"key":"S0218196722500230BIB007","volume-title":"The Book of Traces","author":"Ebinger W.","year":"1995"},{"key":"S0218196722500230BIB008","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803886"},{"key":"S0218196722500230BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02277857"},{"key":"S0218196722500230BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90101-5"},{"key":"S0218196722500230BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0020789"},{"key":"S0218196722500230BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-016-9835-4"},{"key":"S0218196722500230BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"S0218196722500230BIB017","series-title":"Leibniz International Proceedings in Informatics","first-page":"45:1","volume-title":"35th Symp. Theoretical Aspects of Computer Science","volume":"96","author":"K\u00f6cher C.","year":"2018"},{"key":"S0218196722500230BIB018","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2018003"},{"key":"S0218196722500230BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"S0218196722500230BIB020","series-title":"London Mathematical Society Lecture Note Series","first-page":"368","volume-title":"Groups St Andrews","volume":"422","author":"Lohrey M.","year":"2013"},{"key":"S0218196722500230BIB021","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019"},{"key":"S0218196722500230BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45687-2_45"},{"key":"S0218196722500230BIB023","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1964.14.1343"},{"key":"S0218196722500230BIB024","volume-title":"Counter-Free Automata","volume":"65","author":"McNaughton R.","year":"1971"},{"key":"S0218196722500230BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00187-5"},{"key":"S0218196722500230BIB026","first-page":"824","volume":"271","author":"Nivat M.","year":"1970","journal-title":"C. R. Acad. Sci. Paris"},{"key":"S0218196722500230BIB027","first-page":"56","volume":"27","author":"Ochma\u0144ski E.","year":"1985","journal-title":"Bull. EATCS"},{"key":"S0218196722500230BIB028","first-page":"73","volume":"7","author":"Pin J.-\u00c9.","year":"2010","journal-title":"Lect. Notes LIAFA, Univ. Paris"},{"key":"S0218196722500230BIB029","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08555-9"},{"key":"S0218196722500230BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.02.012"},{"key":"S0218196722500230BIB031","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90108-7"},{"key":"S0218196722500230BIB032","first-page":"1","volume-title":"Proc. 5th Annual ACM Symp. on Theory of Computing","author":"Stockmeyer L. J.","year":"1973"},{"key":"S0218196722500230BIB033","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90016-2"},{"key":"S0218196722500230BIB034","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_7"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196722500230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T11:16:25Z","timestamp":1651835785000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196722500230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,24]]},"references-count":31,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["10.1142\/S0218196722500230"],"URL":"https:\/\/doi.org\/10.1142\/s0218196722500230","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,24]]}}}