Paweł Parys - A Type System Describing Unboundedness

dmtcs:4748 - Discrete Mathematics & Theoretical Computer Science, August 18, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-2
A Type System Describing Unboundedness

Authors: Paweł Parys ORCID-iD1

  • 1 Faculty of Mathematics, Informatics, and Mechanics [Warsaw]

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.


Volume: vol. 22 no. 4
Section: Automata, Logic and Semantics
Published on: August 18, 2020
Accepted on: August 3, 2020
Submitted on: August 13, 2018
Keywords: simultaneous-unboundedness problem,higher-order recursion schemes,intersection types,reflection,[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL],[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO],[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]

Linked publications - datasets - softwares

Source : ScholeXplorer IsCitedBy ARXIV 2204.11023
Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.icalp.2022.112
Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2204.11023
  • 10.48550/arxiv.2204.11023
  • 10.4230/lipics.icalp.2022.112
  • 2204.11023
Unboundedness for Recursion Schemes: A Simpler Type System
Barozzini, David ; Parys, Paweł ; Wróblewski, Jan ;

Consultation statistics

This page has been seen 363 times.
This article's PDF has been downloaded 145 times.