{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T10:06:42Z","timestamp":1764842802936,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>A classic result in formal language theory is the equivalence among\nnon-counting, or aperiodic, regular languages, and languages defined through\nstar-free regular expressions, or first-order logic. Past attempts to extend\nthis result beyond the realm of regular languages have met with difficulties:\nfor instance it is known that star-free tree languages may violate the\nnon-counting property and there are aperiodic tree languages that cannot be\ndefined through first-order logic. We extend such classic equivalence results\nto a significant family of deterministic context-free languages, the\noperator-precedence languages (OPL), which strictly includes the widely\ninvestigated visibly pushdown, alias input-driven, family and other structured\ncontext-free languages. The OP model originated in the '60s for defining\nprogramming languages and is still used by high performance compilers; its rich\nalgebraic properties have been investigated initially in connection with\ngrammar learning and recently completed with further closure properties and\nwith monadic second order logic definition. We introduce an extension of\nregular expressions, the OP-expressions (OPE) which define the OPLs and, under\nthe star-free hypothesis, define first-order definable and non-counting OPLs.\nThen, we prove, through a fairly articulated grammar transformation, that\naperiodic OPLs are first-order definable. Thus, the classic equivalence of\nstar-freeness, aperiodicity, and first-order definability is established for\nthe large and powerful class of OPLs. We argue that the same approach can be\nexploited to obtain analogous results for visibly pushdown languages too.<\/jats:p>","DOI":"10.46298\/lmcs-19(4:12)2023","type":"journal-article","created":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T12:30:20Z","timestamp":1700656220000},"source":"Crossref","is-referenced-by-count":2,"title":["Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages"],"prefix":"10.46298","volume":"Volume 19, Issue 4","author":[{"given":"Dino","family":"Mandrioli","sequence":"first","affiliation":[]},{"given":"Matteo","family":"Pradella","sequence":"additional","affiliation":[]},{"given":"Stefano Crespi","family":"Reghizzi","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2023,11,22]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/lmcs.episciences.org\/12584\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/lmcs.episciences.org\/12584\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T12:30:20Z","timestamp":1700656220000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/9684"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,22]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(4:12)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2006.01236v5","asserted-by":"subject"},{"id-type":"arxiv","id":"2006.01236v4","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2006.01236","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2006.01236","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2023,11,22]]},"article-number":"9684"}}