Selected papers

---

Selected papers.

• 2012 Conditional Rényi entropies IEEE Transactions on Information Theory , (accepted for publication)

• 2011 Entropy Measures vs. Kolmogorov Complexity, Entropy, Special Issue on Kolmogorov Complexity, 13(3), pp 595-611.

• 2011 Distinguishing probability ensembles (paper accepted for presentation), Computability in Europe, Sofia 2011.

• 2010 One-way functions using Kolmogorov complexity, Computability in Europe, Azores 2010.

• 2010 Entropy Measures vs. Algorithmic Information, 2010 IEEE International Symposium on Information Theory, (ISIT 2010), Austin, Texas.

• 2010 Kolmogorov Complexity and Entropy Measures, Current Trends in Theory and Practice of Computer Science 2010, 36th International Conference, Czech Republic.

• 2010 The largest monochromatic combinatorial rectangles with applications to Communication Complexity , Computers in Europe 2010, Azores, 2010.

• 2009 Depth as Randomness Deficiency, Theory of Computing Systems, 45:4 pp 724-739.

• 2009 Commitment and authentication systems, Designs, Codes and Cryptography (Springer), 53:3, pp 175-193

• 2007 Computational depth of infinite strings revisited, Proc. CiE 2007, Computational and Logic in the Real World, Siena, 2007.

• 2007 Non-deterministic Communication Complexity and Instance Complexity, Computers in Europe 2007, Siena, 2007.

• 2003 Analysis of a simple reversible language, Theoretical Computer Science, Vol. 290 No. 3, pp 2063-2074.

• 1998 Monadic Logic Programs and Functional Complexity, Theoretical Computer Science, Vol. 176 Nos. 1-2, pp 175-204.

• 1994 A Matrix Model for the Flow of Control in Prolog with Applications to Profiling, Software Practice and Experience, Vol. 24 No. 8, pp 729-746.

• 1994 Periodic sets of Integers, Theoretical Computer Science, Vol. 28 No. 1, pp 577-693.

• 1993 Some Results on the Complexity of SLD-Derivations, in Progress in Artificial Intelligence --6th Portuguese Conference on AI, EPIA'93, M. Filgueiras and L. Damas (eds), Springer-Verlag, 1993.

• 1993 Regular Languages and a Class of Logic Programs, in Progress in Artificial Intelligence --6th Portuguese Conference on AI, EPIA'93, M. Filgueiras and L. Damas (eds), Springer-Verlag, 1993.

   

   

---

Some other papers and talks.

• 2011 Distinguishing two probability ensembles with one sample from each ensemble, (submitted).

• 2005/2011 [pdf] Right associative exponentiation: normal forms and properties, DCC-Faculdade de Ciencias da Universidade do Porto, 2005. Currently (2011) being revised.

• 1091/2011 [pdf] Ackermann and the superpowers, DCC-Faculdade de Engenharia da Universidade do Porto, Currently (2011) being revised.

• 2010 [pdf] (talk) Around descriptive complexity complexity.

• 2010 [pdf] The largest monochromatic combinatorial rectangles with applications to Communication Complexity . Note. This is a slide presentation of a paper cited above.

• 2010 [pdf] Some thoughts about non integral compositional order (working paper)

• 2006 The universal distribution and the average case complexity .

• 2006 [pdf] (talk) Average case, worst case, and the universal distribution .

• 2006 [pdf] (talk) Lower bounds for deterministic communication complexity.

• 2006 [pdf] (talk) Integer reversible transformations.

• 2006 [pdf] A short bibliography on reversibility, DCC-FCUP.

• 2005 [pdf] Semigroup machines: a log n method for recognizing regular expressions , DCC-FCUP.

• 2006 [pdf] Regularity-preserving letter selections, DCC-FCUP Technical Report.

• 2005 [pdf] Kolmogorov complexity in multiplicative arithmetic, (preliminary version), DCC-FCUP Technical Report, 2005.

• 2001 [pdf] A Turing machine model where the duality between determinism and reversibility is explicit, (preliminary version), DCC-FCUP Internal Report.

• 2001 [pdf] Explicit formulas for the Shannon and Rényi entropies of some non independent sources of symbols, (preliminary version), EPPIA.

• 2000 [pdf] On the number of lines of the Theorems of the formal system MIU, (preliminary version), DCC-FCUP Internal Report.