Pablo Ariel Heiber
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Pablo Ariel Heiber has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Verónica Becher
Instituto de Ciencias de la Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires & CONICET, Buenos Aires C1428EGA, Argentina
7 shared publications - Theodore A. Slaman
Department of Mathematics, University of California, Berkeley, Berkeley, California 94720-3840
3 shared publications - Olivier Carton
Institut universitaire de France et IRIF, Université Paris-Cité, France
2 shared publications Alejandro Deymonnaz
Departamento de Computación Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires Argentina
1 shared publication
Latest Publications
- Open Access
Finite-state independence
In this work we introduce a notion of independence based on finite-state automata: two infinite words are independent if no one helps to compress the other using one-to-one finite-state transducers with auxiliary input. We prove that, as expected, the set of independent pairs of infinite words has Lebesgue measure 1. We show that the join of two independent normal words is normal. However, the independence of two normal words is not guaranteed if we just require that their join is normal. To prove this we construct a normal word $x_1x_2x_3\ldots$ where $x_{2n}=x_n$ for every $n$.Open AccessFinite-state independence
In this work we introduce a notion of independence based on finite-state automata: two infinite words are independent if no one helps to compress the other using one-to-one finite-state transducers with auxiliary input. We prove that, as expected, the set of independent pairs of infinite words has Lebesgue measure 1. We show that the join of two independent normal words is normal. However, the independence of two normal words is not guaranteed if we just require that their join is normal. To prove this we construct a normal word $x_1x_2x_3\ldots$ where $x_{2n}=x_n$ for every $n$. - 1 December 2015
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 81 (8) , 1592-1613
Normality and automata
- 1 December 2015
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 81 (8) , 1592-1613
Normality and automata
- Open Access
- 24 April 2015
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 84 (296) , 2939-2952
A computable absolutely normal Liouville number
We give an algorithm that computes an absolutely normal Liouville number.
- 24 April 2015
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 84 (296) , 2939-2952
Open AccessA computable absolutely normal Liouville number
We give an algorithm that computes an absolutely normal Liouville number.
- Open Access
Normal Numbers and the Borel Hierarchy
We show that the set of absolutely normal numbers is $\mathbf \Pi^0_3$-complete in the Borel hierarchy of subsets of real numbers. Similarly, the set of absolutely normal numbers is $\Pi^0_3$-complete in the effective Borel hierarchy.
Open AccessNormal Numbers and the Borel Hierarchy
We show that the set of absolutely normal numbers is $\mathbf \Pi^0_3$-complete in the Borel hierarchy of subsets of real numbers. Similarly, the set of absolutely normal numbers is $\Pi^0_3$-complete in the effective Borel hierarchy.
- 1 November 2013
- Published by Elsevier in Information and Computation
- Vol. 232, 1-9
A polynomial-time algorithm for computing absolutely normal numbers
- 1 November 2013
- Published by Elsevier in Information and Computation
- Vol. 232, 1-9
A polynomial-time algorithm for computing absolutely normal numbers
- Open Access
Efficient repeat finding via suffix arrays
We solve the problem of finding interspersed maximal repeats using a suffix array construction. As it is well known, all the functionality of suffix trees can be handled by suffix arrays, gaining practicality. Our solution improves the suffix tree based approaches for the repeat finding problem, being particularly well suited for very large inputs. We prove the corrrectness and complexity of the algorithms.
Open AccessEfficient repeat finding via suffix arrays
We solve the problem of finding interspersed maximal repeats using a suffix array construction. As it is well known, all the functionality of suffix trees can be handled by suffix arrays, gaining practicality. Our solution improves the suffix tree based approaches for the repeat finding problem, being particularly well suited for very large inputs. We prove the corrrectness and complexity of the algorithms.
- 28 March 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 438, 62-73
A linearly computable measure of string complexity
- 28 March 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 438, 62-73
A linearly computable measure of string complexity