Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyCost Automata, Safe Schemes, and Downward Closures
| cris.lastimport.scopus | 2024-02-12T19:02:22Z |
| dc.abstract.en | In this work we prove decidability of the model-checking problem for safe recursion schemes against properties defined by alternating B-automata. We then exploit this result to show how to compute downward closures of languages of finite trees recognized by safe recursion schemes. Higher-order recursion schemes are an expressive formalism used to define languages of finite and infinite ranked trees by means of fixed points of lambda terms. They extend regular and context-free grammars, and are equivalent in expressive power to the simply typed λY-calculus and collapsible pushdown automata. Safety in a syntactic restriction which limits their expressive power. The class of alternating B-automata is an extension of alternating parity automata over infinite trees; it enhances them with counting features that can be used to describe boundedness properties. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Parys, Paweł |
| dc.contributor.author | Colcombet, Thomas |
| dc.contributor.author | Clemente, Lorenzo |
| dc.contributor.author | Barozzini, David |
| dc.date.accessioned | 2024-01-24T20:53:28Z |
| dc.date.available | 2024-01-24T20:53:28Z |
| dc.date.issued | 2023 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.number | 3 |
| dc.description.volume | 188 |
| dc.identifier.doi | 10.3233/FI-222145 |
| dc.identifier.issn | 0169-2968 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/103812 |
| dc.identifier.weblink | https://doi.org/10.4230/LIPIcs.ICALP.2020.109 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.ispartof | Fundamenta Informaticae |
| dc.relation.pages | 127-178 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | Cost logics |
| dc.subject.en | cost automata |
| dc.subject.en | downward closures |
| dc.subject.en | higher-order recursion schemes |
| dc.subject.en | safe recursion schemes |
| dc.title | Cost Automata, Safe Schemes, and Downward Closures |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |