1 citations · 1 across the 6 of their papers we have counts for
6 papers
Splitting recursion schemes into reversible and classical interacting threads
Armando B. Matos, Luca Paolini, Luca Roversi
Given a simple recursive function, we show how to extract from it a reversible and an classical iterative part. Those parts can synchronously cooperate under a Producer/Consumer pa…
Interleaving classical and reversible
Armando B. Matos, Luca Paolini, Luca Roversi
Given a simple recursive function, we show how to extract two interacting processes from it. The two processes can be described by means of iterative programs, one of which is intr…
Primitive recursive functions versus partial recursive functions: comparing the degree of undecidability
Armando B. Matos
Consider a decision problem whose instance is a function. Its degree of undecidability, measured by the corresponding class of the arithmetic (or Kleene-Mostowski) hierarchy hierar…
Measuring communication complexity using instance complexity with oracles
Armando Matos, Andreia Teixeira, Andre Souto
We establish a connection between non-deterministic communication complexity and instance complexity, a measure of information based on algorithmic entropy. Let , $\o…
Entropy Measures vs. Algorithmic Information
Andreia Teixeira, Andre Souto, Armando Matos +1
Algorithmic entropy and Shannon entropy are two conceptually different information measures, as the former is based on size of programs and the later in probability distributions.…
Depth as Randomness Deficiency
Luis Antunes, Armando Matos, Andre Souto +1
Depth of an object concerns a tradeoff between computation time and excess of program length over the shortest program length required to obtain the object. It gives an uncondition…