{"authors":[{"id":null,"fullName":"Nieuwveld, J.","name":"J.","surname":"Nieuwveld","rank":1,"pid":null},{"id":null,"fullName":"Ouaknine, J.","name":"J.","surname":"Ouaknine","rank":2,"pid":null}],"openAccessColor":null,"publiclyFunded":false,"eoscIfGuidelines":null,"type":"publication","language":{"code":"und","label":"Undetermined"},"countries":[{"code":"DE","label":"Germany","provenance":null}],"subjects":[{"subject":{"scheme":"keyword","value":"linear recurrence sequences"},"provenance":null},{"subject":{"scheme":"keyword","value":"FOS: Computer and information sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"Logic in Computer Science"},"provenance":null},{"subject":{"scheme":"keyword","value":"decidability"},"provenance":null},{"subject":{"scheme":"FOS","value":"0102 computer and information sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"11B37 11J86 11B40 11K16"},"provenance":null},{"subject":{"scheme":"FOS","value":"01 natural sciences"},"provenance":null},{"subject":{"scheme":"keyword","value":"Logic in Computer Science (cs.LO)"},"provenance":null},{"subject":{"scheme":"keyword","value":"F.4.0; G.2.0"},"provenance":null},{"subject":{"scheme":"keyword","value":"Number Theory"},"provenance":null},{"subject":{"scheme":"keyword","value":"FOS: Mathematics"},"provenance":null},{"subject":{"scheme":"keyword","value":"Baker’s theorem"},"provenance":null},{"subject":{"scheme":"keyword","value":"Monadic second-order logic"},"provenance":null},{"subject":{"scheme":"keyword","value":"Number Theory (math.NT)"},"provenance":null}],"mainTitle":"On Expansions of Monadic Second-Order Logic with Dynamical Predicates","subTitle":null,"descriptions":["Expansions of the monadic second-order (MSO) theory of the structure $\\langle \\mathbb{N} ; < \\rangle$ have been a fertile and active area of research ever since the publication of the seminal papers of Büchi and Elgot & Rabin on the subject in the 1960s. In the present paper, we establish decidability of the MSO theory of $\\langle \\mathbb{N} ; <,P \\rangle$, where $P$ ranges over a large class of unary ''dynamical'' predicates, i.e., sets of non-negative values assumed by certain integer linear recurrence sequences. One of our key technical tools is the novel concept of (effective) prodisjunctivity, which we expect may also find independent applications further afield.","Full version of a paper accepted to MFCS 2025"],"publicationDate":"2025-01-01","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","embargoEndDate":"2025-07-01","sources":["Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science","Leibniz International Proceedings in Informatics"],"formats":["application/pdf"],"contributors":["Joris Nieuwveld and Joël Ouaknine"],"coverages":null,"bestAccessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/"},"container":{"name":"CoRR","issnPrinted":null,"issnOnline":null,"issnLinking":null,"ep":null,"iss":null,"sp":null,"vol":"abs/2507.16581","edition":null,"conferencePlace":null,"conferenceDate":null},"documentationUrls":null,"codeRepositoryUrl":null,"programmingLanguage":null,"contactPeople":null,"contactGroups":null,"tools":null,"size":null,"version":null,"geoLocations":null,"id":"doi_dedup___::d5131ecaf5acbbad330d00e05a7f94be","originalIds":["50|datacite____::d5131ecaf5acbbad330d00e05a7f94be","10.48550/arxiv.2507.16581","50|od________18::5f53155c24cc82396f0f337880911963","oai:arXiv.org:2507.16581","50|dblp________::4c965f0bc936a0c34d11830dc234804a","50|dblp________::a795bf39106d863f8564e1aa2e42ee7f","50|od______1814::26d552768f799878ddedb8e0bc500420","oai:drops-oai.dagstuhl.de:24187","50|od______1874::17072d9d8a7065a58600a093bddaed87","oai:pure.mpg.de:item_3667572","50|userclaim___::d5131ecaf5acbbad330d00e05a7f94be"],"pids":[{"scheme":"doi","value":"10.48550/arxiv.2507.16581"},{"scheme":"arXiv","value":"2507.16581"},{"scheme":"handle","value":"21.11116/0000-0011-B2C1-9"},{"scheme":"handle","value":"21.11116/0000-0011-B2BF-D"}],"dateOfCollection":null,"lastUpdateTimeStamp":null,"indicators":{"citationImpact":{"citationCount":0.0,"influence":2.1746283E-9,"popularity":2.2497804E-9,"impulse":0.0,"citationClass":"C5","influenceClass":"C5","impulseClass":"C5","popularityClass":"C5"}},"projects":[{"id":"corda_____he::3c887167beefeb628ffd5f0a95de5cf5","code":"101167561","acronym":"DynAMiCs","title":"Dynamical and Arithmetical Model Checking","funder":"European Commission","pids":[{"scheme":"doi","value":"10.3030/101167561"}]},{"id":"dfgf________::2c3b3a6732c9f03c8caa60f094654de7","code":"389792660/TRR 248","acronym":null,"title":"Foundations of Perspicuous Software Systems - Enabling Comprehension in a Cyber-Physical World","funder":"Deutsche Forschungsgemeinschaft","pids":null}],"organizations":[{"legalName":"Leibniz Association","acronym":"LG","id":"openorgs____::f19bd4f95b81943353a480436ef88fd0","pids":[{"scheme":"GRID","value":"grid.413453.4"},{"scheme":"OrgReg","value":"DE1086"},{"scheme":"Wikidata","value":"Q680090"},{"scheme":"fundref","value":"501100001664"},{"scheme":"ROR","value":"https://ror.org/01n6r0e97"},{"scheme":"ISNI","value":"0000000122243060"},{"scheme":"OrgRef","value":"2443230"},{"scheme":"wikidata","value":"Q680090"},{"scheme":"FundRef","value":"501100001664"},{"scheme":"mag_id","value":"315704651"}],"countries":[{"code":"DE","label":"Germany"}],"websiteurl":"http://www.leibniz-gemeinschaft.de/en/home/"},{"legalName":"Schloss Dagstuhl – Leibniz Center for Informatics","acronym":"IBFI","id":"openorgs____::98c791d123e9b6f3e3eadbb4ae60e529","pids":[{"scheme":"wikidata","value":"Q879857"},{"scheme":"OrgReg","value":"DE1207"},{"scheme":"GRID","value":"grid.469874.0"},{"scheme":"PIC","value":"889869368"},{"scheme":"Wikidata","value":"Q879857"},{"scheme":"ROR","value":"https://ror.org/00k4h2615"},{"scheme":"mag_id","value":"2799853480"},{"scheme":"ISNI","value":"0000000100093196"}],"countries":[{"code":"DE","label":"Germany"}],"websiteurl":"https://www.dagstuhl.de/en/"},{"legalName":"Max Planck Institute for Software Systems","acronym":"MPI-SWS","id":"openorgs____::a6be3b23fdb0e61554b444ec8c1e8d1c","pids":[{"scheme":"Wikidata","value":"Q881238"},{"scheme":"GRID","value":"grid.469860.5"},{"scheme":"ISNI","value":"000000040492020X"},{"scheme":"ROR","value":"https://ror.org/02pe2kf23"},{"scheme":"wikidata","value":"Q881238"}],"countries":[{"code":"DE","label":"Germany"}],"websiteurl":"https://www.mpi-sws.org/index.php"},{"legalName":"Max Planck Society","acronym":"MPG","id":"openorgs____::5a405a89387d1881afa956f475994e10","pids":[{"scheme":"ISNI","value":"0000000121051091"},{"scheme":"ROR","value":"https://ror.org/01hhn8329"},{"scheme":"GRID","value":"grid.4372.2"},{"scheme":"PIC","value":"999990267"},{"scheme":"RRID","value":"RRID:nlx_55250"},{"scheme":"FundRef","value":"501100004189"},{"scheme":"RRID","value":"RRID:SCR_011366"},{"scheme":"Wikidata","value":"Q158085"},{"scheme":"OrgRef","value":"614753"},{"scheme":"mag_id","value":"149899117"},{"scheme":"wikidata","value":"Q158085"},{"scheme":"fundref","value":"501100004189"}],"countries":[{"code":"DE","label":"Germany"}],"websiteurl":"http://www.mpg.de/en"}],"communities":null,"collectedFrom":[{"key":"openaire____::9e3be59865b2c1c335d32dae2fe7b254","value":"Datacite"},{"key":"opendoar____::155fa09596c7e18e50b58eb7e0c6ccb4","value":"Dagstuhl Research Online Publication Server"},{"key":"opendoar____::958adb57686c2fdec5796398de5f317a","value":"MPG.PuRe"},{"key":"infrastruct_::f66f1bd369679b5b077dcdf006089556","value":"OpenAIRE"},{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"}],"instances":[{"pids":[{"scheme":"doi","value":"10.48550/arxiv.2507.16581"}],"license":"CC BY","type":"Article","urls":["https://dx.doi.org/10.48550/arxiv.2507.16581"],"publicationDate":"2025-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::55045bd2a65019fd8e6741a755395c8c","value":"Unknown Repository"},"collectedFrom":{"key":"openaire____::9e3be59865b2c1c335d32dae2fe7b254","value":"Datacite"}},{"pids":[{"scheme":"arXiv","value":"2507.16581"}],"accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":null},"type":"Preprint","urls":["http://arxiv.org/abs/2507.16581"],"publicationDate":"2025-07-22","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"},"collectedFrom":{"key":"opendoar____::6f4922f45568161a8cdf4ad2299f6d23","value":"arXiv.org e-Print Archive"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.48550/arxiv.2507.16581"}],"type":"Preprint","urls":["https://doi.org/10.48550/arXiv.2507.16581","https://dblp.org/rec/journals/corr/abs-2507-16581.html"],"publicationDate":"2025-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},"collectedFrom":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.4230/lipics.mfcs.2025.80"}],"type":"Conference object","urls":["https://doi.org/10.4230/LIPIcs.MFCS.2025.80","https://dblp.org/rec/conf/mfcs/NieuwveldO25.html"],"refereed":"nonPeerReviewed","hostedBy":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"},"collectedFrom":{"key":"openaire____::d8b68cc0a53121f6f896883a7d60c1db","value":"DBLP"}},{"alternateIdentifiers":[{"scheme":"doi","value":"10.4230/lipics.mfcs.2025.80"}],"license":"CC BY","type":"Conference object","urls":["https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.80"],"publicationDate":"2025-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::155fa09596c7e18e50b58eb7e0c6ccb4","value":"Dagstuhl Research Online Publication Server"},"collectedFrom":{"key":"opendoar____::155fa09596c7e18e50b58eb7e0c6ccb4","value":"Dagstuhl Research Online Publication Server"}},{"pids":[{"scheme":"handle","value":"21.11116/0000-0011-B2C1-9"},{"scheme":"handle","value":"21.11116/0000-0011-B2BF-D"}],"alternateIdentifiers":[{"scheme":"doi","value":"10.4230/lipics.mfcs.2025.80"}],"license":"CC BY","accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":null},"type":"Conference object","urls":["https://hdl.handle.net/21.11116/0000-0011-B2BF-D","https://hdl.handle.net/21.11116/0000-0011-B2C1-9"],"publicationDate":"2025-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"opendoar____::958adb57686c2fdec5796398de5f317a","value":"MPG.PuRe"},"collectedFrom":{"key":"opendoar____::958adb57686c2fdec5796398de5f317a","value":"MPG.PuRe"}},{"pids":[{"scheme":"handle","value":"21.11116/0000-0011-B2C1-9"},{"scheme":"handle","value":"21.11116/0000-0011-B2BF-D"}],"alternateIdentifiers":[{"scheme":"doi","value":"10.48550/arxiv.2507.16581"},{"scheme":"arXiv","value":"2507.16581"}],"accessRight":{"code":"c_abf2","label":"OPEN","scheme":"http://vocabularies.coar-repositories.org/documentation/access_rights/","openAccessRoute":null},"type":"Article","urls":["https://dx.doi.org/10.48550/arxiv.2507.16581"],"publicationDate":"2025-01-01","refereed":"nonPeerReviewed","hostedBy":{"key":"infrastruct_::f66f1bd369679b5b077dcdf006089556","value":"OpenAIRE"},"collectedFrom":{"key":"infrastruct_::f66f1bd369679b5b077dcdf006089556","value":"OpenAIRE"}}],"links":[{"header":{"relationType":"resultProject","relationClass":"isProducedBy","relatedIdentifier":"corda_____he::3c887167beefeb628ffd5f0a95de5cf5","relatedRecordType":"project","relationProvenance":"user:claim","trust":"0.9"},"collectedfrom":[{"dsId":"openaire____::3f264f93cf3b0cfc4ede188a6300455c","dsName":"CORDA - COmmon Research DAta Warehouse - Horizon Europe"}],"projectTitle":"Dynamical and Arithmetical Model Checking","code":"101167561","funding":{"funder":{"id":"ec__________::EC","shortname":"EC","name":"European Commission","jurisdiction":{"code":"EU","label":"European Union"},"pid":null},"level0":{"id":"ec__________::EC::HE","description":"Horizon Europe Framework Programme","name":"HE"},"level1":{"id":"ec__________::EC::HE::ERC","description":"European Research Council","name":"ERC"},"level2":{"id":"ec__________::EC::HE::ERC::HORIZON-ERC-SYG","description":"HORIZON ERC Synergy Grants","name":"HORIZON-ERC-SYG"}},"startDate":"2025-05-01","endDate":"2031-04-30"},{"header":{"relationType":"resultProject","relationClass":"isProducedBy","relatedIdentifier":"dfgf________::2c3b3a6732c9f03c8caa60f094654de7","relatedRecordType":"project","relationProvenance":"iis","trust":"0.72"},"collectedfrom":[{"dsId":"openaire____::513d203da49f316ec241afa087643a02","dsName":"Deutsche Forschungsgemeinschaft"}],"projectTitle":"Foundations of Perspicuous Software Systems - Enabling Comprehension in a Cyber-Physical World","code":"389792660/TRR 248","funding":{"funder":{"id":"dfgf________::DFG","shortname":"DFG","name":"Deutsche Forschungsgemeinschaft","jurisdiction":{"code":"DE","label":"Germany"},"pid":null},"level0":{"id":"dfgf________::DFG::281a47b1e4d1be198a79d31842181bad","description":"Transregios","name":"Transregios"},"level1":{"id":null,"description":null,"name":null},"level2":{"id":null,"description":null,"name":null}},"startDate":"2019-01-01"}],"otherTitles":null,"inDiamondJournal":false,"green":true,"isGreen":true,"isInDiamondJournal":false}