{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:37:35Z","timestamp":1753889855427,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Automata, Logic and Semantics","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,4,1]]},"abstract":"<jats:p xml:lang=\"en\">We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We propose a type system that allows to solve the simultaneous-unboundedness problem (SUP) for schemes, which asks, given a set of letters A and a scheme G, whether it is the case that for every number n the scheme accepts a word (a tree) in which every letter from A appears at least n times. Using this type system we prove that SUP is (m-1)-EXPTIME-complete for word-recognizing schemes of order m, and m-EXPTIME-complete for tree-recognizing schemes of order m. Moreover, we establish the reflection property for SUP: out of an input scheme G one can create its enhanced version that recognizes the same language but is aware of the answer to SUP.<\/jats:p>","DOI":"10.23638\/dmtcs-22-4-2","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:53:30Z","timestamp":1743699210000},"source":"Crossref","is-referenced-by-count":0,"title":["A Type System Describing Unboundedness"],"prefix":"10.23638","volume":"vol. 22 no. 4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7247-1408","authenticated-orcid":false,"given":"Pawe\u0142","family":"Parys","sequence":"first","affiliation":[{"name":"Faculty of Mathematics, Informatics, and Mechanics [Warsaw]"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2020,8,18]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/hal.science\/hal-01850934v4\/document","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/hal.science\/hal-01850934v4\/document","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:53:30Z","timestamp":1743699210000},"score":1,"resource":{"primary":{"URL":"http:\/\/dmtcs.episciences.org\/4748"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,18]]},"references-count":0,"journal-issue":{"issue":"Automata, Logic and Semantics","published-online":{"date-parts":[[2020,8,18]]}},"URL":"https:\/\/doi.org\/10.23638\/dmtcs-22-4-2","relation":{"has-preprint":[{"id-type":"uri","id":"https:\/\/hal.science\/hal-01850934v3","asserted-by":"subject"},{"id-type":"uri","id":"https:\/\/hal.science\/hal-01850934v2","asserted-by":"subject"},{"id-type":"uri","id":"https:\/\/hal.science\/hal-01850934v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"uri","id":"https:\/\/hal.science\/hal-01850934v4","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"type":"electronic","value":"1365-8050"}],"subject":[],"published":{"date-parts":[[2020,8,18]]},"article-number":"4748"}}