{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:39:32Z","timestamp":1753889972625,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,9,17]],"date-time":"2015-09-17T00:00:00Z","timestamp":1442448000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The notion of orbit finite data monoid was recently introduced by Bojanczyk\nas an algebraic object for defining recognizable languages of data words.\nFollowing Buchi's approach, we introduce a variant of monadic second-order\nlogic with data equality tests that captures precisely the data languages\nrecognizable by orbit finite data monoids. We also establish, following this\ntime the approach of Schutzenberger, McNaughton and Papert, that the\nfirst-order fragment of this logic defines exactly the data languages\nrecognizable by aperiodic orbit finite data monoids. Finally, we consider\nanother variant of the logic that can be interpreted over generic structures\nwith data. The data languages defined in this variant are also recognized by\nunambiguous finite memory automata.<\/jats:p>","DOI":"10.2168\/lmcs-11(3:10)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T13:46:02Z","timestamp":1479735962000},"source":"Crossref","is-referenced-by-count":3,"title":["Logics with rigidly guarded data tests"],"prefix":"10.46298","volume":"Volume 11, Issue 3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9831-3264","authenticated-orcid":false,"given":"Gabriele","family":"Puppis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6529-6963","authenticated-orcid":false,"given":"Thomas","family":"Colcombet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clemens","family":"Ley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2015,9,17]]},"reference":[{"key":"1080:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1586\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1586\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:07:14Z","timestamp":1681243634000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1586"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,17]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(3:10)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1410.2022","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1410.2022","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,9,17]]},"article-number":"1586"}}