|
-
[2018] -
Preliminary Notes: Wires of reversible digital circuits and
programming registers of reversible languages.
(ℵ, 1).
-
[2018] -
List of Technical Reports on reversible SRL-like programming
languages.
(1,
11,12
).
Abstracts and tables of contents here.
-
[2018] -
The Fixed Point Problem for General and for Linear SRL Programs is Undecidable.
(1,11,12).
Proceedings of the 19th Italian Conference on Theoretical Computer Science
Urbino, Italy, 2018. Edited by Alessandro Aldini and Marco Bernardo.
http://ceur-ws.org/Vol-2243/
-
[2017] -
Note on the current research in total reversible programming languages.
Collaboration with Luca Roversi and Luca Paolini
(1,11,12).
-
[2017] -
Howard, The formulae-as-types notion of construction [Howard, 1969].
For personal study only;
sfumato version.
(ℵ, 1).
-
[2017] -
Some old papers transcribed to Latex (with comments).
(ℵ, 1).
-
[2016] -
The most difficult Sudoku puzzles are quickly solved
by a straightforward depth-first search algorithm.
(1).
Run the algorithms:
README
,
programs and files.
-
[2015] -
Is there a "Rice-like Theorem" for primitive recursive (PR) functions?.
(ℵ,
1).
-
[2015] -
Effective operations on partial functions -
transcriptions for study with personal comments.
(ℵ, 1).
-
[2015] -
On ordinal numbers, transcriptions of [Rogers (1989)].
For personal study.
(ℵ, 1).
-
[2014] -
Turing Princeton PhD dissertation converted to $\LaTeX$
(available in in Andrew Hodges page)
(ℵ, 1).
-
[2014] -
Programs with infinite loops: from the infinite recursive
predicates to the arithmetic hierarchy.
(ℵ, 1).
-
[2014] -
The inverse of the Ackermann function
is primitive recursive.
(ℵ, 1).
-
[2014/2015] -
Closed form of primitive recursive functions:
from imperative programs
to mathematical expressions
to functional programs.
(only some pages)
(ℵ, 1).
-
[2014] -
Topics in recursion theory:
primitive recursion, Kleene normal form,
arithmetical definability, arithmetical hierarchy, complete
sets....
(ℵ, 1).
-
[2014] -
Understanding a paper by William Craig.
(ℵ, 1).
-
[2014] -
On the Kleene normal form.
(ℵ, 1).
-
[2014] -
Register reversible languages, work in progress.
(ℵ, 1).
-
[2014] -
On the Kolmogorov complexity of formal proofs
(file not available).
(1).
-
[2014] -
Direct proofs of Rice's theorem.
(ℵ, 1).
-
[2011] -
Entropy Measures vs. Kolmogorov Complexity.
(2,
1,
6,
8,
9).
Entropy, Special Issue on Kolmogorov Complexity,
13(3), pp 595-611.
-
[2011] -
Distinguishing probability ensembles.
(8,
9,
1).
Computability in Europe, Sofia 2011.
-
[2011/2015] -
Distinguishing two probability ensembles
with one sample from each ensemble.
Theory_of_Computing_Systems, 10/2015;
Vol 57, pp 1-15
(2,
3,
1,
8,
9).
-
[2010] -
One-way functions using Kolmogorov complexity.
(6,
8,
9).
Computability in Europe, Azores 2010.
-
[2010] -
Entropy Measures vs. Algorithmic Information.
(8,
9,
1,
2).
2010 IEEE International Symposium on Information Theory, (ISIT 2010),
Austin, Texas.
-
[2010] -
Kolmogorov Complexity and Entropy Measures.
(2,
1,
8,
9).
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.
(1,
9).
Computers in Europe 2010, Azores, 2010.
-
[2009] -
Depth as Randomness Deficiency.
(2,
1,
8.
10).
Theory of Computing Systems, 45:4
pp 724-739.
-
[2009] -
Commitment and authentication systems.
(6,
8,
1,
2).
Designs, Codes and Cryptography (Springer),
53:3, pp 175-193.
-
[2009] -
Measuring communication complexity using instance
complexity with oracles.
(1,
9,
8).
Computing Research Repository - CORR
Vol 0901.2, 2009.
-
[2009] -
Talk: Average case, worst case, and the universal
distribution.
(1).
DCC-Faculdade de Ciencias da Universidade do Porto.
-
[2007] -
Non-deterministic Communication Complexity and Instance
Complexity.
(1,
8,
9).
Computers in Europe 2007, Siena, 2007.
-
[2007] -
Computational depth of
infinite strings revisited.
(2,
11,
1,
10).
Proc. CiE 2007, Computational and Logic in the Real World,
Siena, 2007.
-
[1998] -
Monadic Logic Programs and Functional Complexity.
(1).
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.
(1).
Software Practice and Experience,
Vol. 24 No. 8, pp 729-746.
-
[1994]
Periodic sets of Integers.
(1).
Theoretical Computer Science, Vol. 28 No. 1,
pp 577-693.
-
[1994] -
An introduction to ultimately periodic sets of integers
(1).
ACM SIGACT News, Volume 25 Issue 1, March 1994, pp 90-96.
-
[1993]
Some Results on the Complexity of SLD-Derivations.
(1).
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.
(1).
In
Progress in Artificial Intelligence -
6th Portuguese Conference on AI, EPIA'93,
M. Filgueiras and L. Damas (eds), Springer-Verlag, 1993.
-
[1980, lastest revision: 2015] -
Ackermann and the superpowers.
(7,
1).
DCC-Faculdade de Engenharia da Universidade do Porto,
Previous version published in "SIGACT, IEEE".
Top of page!
Notes.
Authors:
(1) Armando Matos
(2) Luís Antunes
(3) Henry Buhrman
(4) Armindo Costa
(5) Nelma Moreira
(12) Luca Paolini
(6) Alexandre Pinto
(7) António Porto
(11) Luca Roversi
(8) André Souto
(9) Andreia Teixeira
(10) Paul Vitányi
[P] In Portuguese.
(ℵ) May contain transcriptions of other works. Read at your own risk.
"The power of instruction is seldom of much efficacy except in those happy dispositions where it is almost superfluous", Gibbon
"Le temps est un grand maître, dit-on; le malheur est qu'il soit un
maître inhumain qui tue ses élèves", Berlioz
Sunday 16 December 2018
(27893 accesses)
Identity problem: the security code
is still encrypted; you seem to be
either a visitor without a number or a number without a
visitor; please try again.
|
/
Author, co-authors: links like these:
