Armando B. Matos

A. Matos homepage

Magister dixit: "nullius in verba"


Armando B. Matos
$ Display all 3194 possibilities? (y or n)

Researcher and retired teacher, email: reverse "moc.oohay@mcbodnamra"
LIACC, Artificial Intelligence Computer Science Laboratory / Computer Science Department / Faculty of Sciences / FCUP info / Universidade do Porto / Porto

	Papers (below)			易
	reversible languages: work in progress (pdf)			Course: “Topics on Advanced Algorithms”
	reversible languages: TCS paper (pdf)			Course: “Introductory Programming”
	...A text on advanced algorithms (pdf).			Course: “Complexity”
	Mathoverflow			Course: “Imperative Programming”
	Research on primitive recursive functions			C.A.R. Hoare on categories (only for my study)
	Pr. recursive functions: implementation efficiency			Logicians discussing weak arithmetics
	AI & CS Lab, LIACC, Univ. Porto			Consequences of Godel's Incompleteness Theorem
	Programming is useful...			Panflation!
	List of quotes...

Some links: “Porto: folios” / -> / * / O / T / B / R / S / C / L / N / 1 / 2 / Opti / ? / . $\sum_{i=0}^{75}{\rm quote}^{i\pi}(i)=\frac{i\tau}{\omega} \Xi^\text{dubious} \rho$ "Random" quote: Donald E. Knuth: I'm worried about the present state of programming. Programmers now are supposed to mostly just use libraries. Programmers aren't allowed to do their own thing from scratch anymore. They are supposed to assemble reusable code that somebody else has written. There's a bunch of things on the menu and you chose from these and put them together. Where's the fun in that? Where's the beauty in that? We have to figure out a way we can make programming interesting for the next generation of programmers.

List of papers, research notes, and research description: year ≥ 1993 (earlier dates: please search here):

Links are underlined / To see an abstract or summary: gently hover over the title! Test here / Published (journal or conference) or submitted: / Author, co-authors: links like these: (2), (1).

[2016] - https://arxiv.org/abs/1607.01686
Primitive recursive functions versus partial recursive functions:
comparing the degree of undecidability (1).

[2016] - Total recursive functions that are not primitive recursive. For personal study. (ℵ, 1).

[2015] - The efficiency of primitive recursive functions; a programmer's view.
Theoretical Computer Science, Vol 564, August 2015, pages 65-81 (1).
[2011/2015] - Distinguishing two probability ensembles with one sample from each ensemble.
Theory of Computing Systems, 10/2015; See below. (2, 3, 1, 8, 9).

[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).

[2013] - One-way functions using Algorithm and Classical Information Theories. (2, 1, 6, 8, 9).
Theory of Computing Systems, Vol 52, n. 1, pages 162-178, 2013.

[2013] - Versions of Godel's incompleteness Theorem. (ℵ, 1).
[2013] - On a paper by Leonard Adleman. (1).
[2013] - The relationship between logic and complexity classes. (ℵ, 1).
[2013] - Introduction to Category Theory. (ℵ, 1).
[2013/2014] - Primitive recursive functions: decidability problems. [a FEW PAGES ONLY!]. (1).

[2012] - Conditional Renyi entropies. (1, 9, 1, 2).
IEEE Transactions on Information Theory Vol 58, issue 7.

[2012] - A bibliography on sub-recursive classes. (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.

[2010] - Talk: Around descriptive complexity complexity. (1).
DCC-Faculdade de Ciencias da Universidade do Porto.

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

[2010] - About non integral compositional order [working paper]. (1).
DCC-Faculdade de Ciencias da Universidade do Porto.

[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.

[2007] - [P] Notas sobre minorantes de complexidade. (1).
DCC-Faculdade de Ciencias da Universidade do Porto.
[2006] - [P] Algumas notas sobre a teoria dos problemas completos na classe NP. (1).
DCC-Faculdade de Ciencias da Universidade do Porto.
[2006] - [P] Complexidade e criptografia, (1).
DCC-Faculdade de Ciencias da Universidade do Porto.

[2006] - Galois Field Commitment Scheme. (6, 8, 1, 2). ,
IACR Cryptology ePrint Archive; 2006:410.

[2006] - A short bibliography on reversibility. (1). DCC-Faculdade de Ciencias da Universidade do Porto.
[2006] - [revised in 2012] Monoid machines: a log n method for recognizing regular expressions. (1).
DCC-Faculdade de Ciencias da Universidade do Porto.
[2006] - Regularity-preserving letter selections. (1).
DCC-Faculdade de Ciencias da Universidade do Porto, Technical Report.
[2006] - Talk: Lower bounds for deterministic communication. (1).
DCC-Faculdade de Ciencias da Universidade do Porto.
[2005] - Kolmogorov complexity in multiplicative arithmetic. (1).
DCC-Faculdade de Ciencias da Universidade do Porto, Technical Report.
[2005] - [revised in 2011] Right associative exponentiation: normal forms and properties. (1).
DCC-Faculdade de Ciencias da Universidade do Porto.
[2004] - [P] Introducao `a Complexidade de Kolmogorov. (5, 1).
DCC-Faculdade de Ciencias da Universidade do Porto.
[2004] - [P] Computabilidade e Teoria da Recursao. (5, 1).
DCC-Faculdade de Ciencias da Universidade do Porto.
[2004] - [P] Teoria dos problemas completos na classe NP. (5, 1).
DCC-Faculdade de Ciencias da Universidade do Porto.

[2003] - Linear programs in a simple reversible language. (1).
Theoretical Computer Science, Vol. 290 No. 3, pp 2063-2074.

[2002 (this version)] Trying to solve Peg Solitaire by a simple, depth-first search. (1).
DCC-Faculdade de Ciencias da Universidade do Porto.
[2001/2014] - A Turing machine model where the duality between determinism and reversibility is explicit. (preliminary version). (1).
DCC-Faculdade de Ciencias da Universidade do Porto, Internal Report.

[2001] - Explicit formulas for the Shannon and Renyi entropies of some non independent sources of symbols, (preliminary version). (2, 1).
EPPIA.

[2000] - On the number of lines of the Theorems of the formal system MIU (preliminary version). (2, 1).
DCC-Faculdade de Ciencias da Universidade do Porto Internal Report.

[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 Wednesday 19 September 2018 (27403 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.

Magister dixit: "nullius in verba"

易

List of papers, research notes, and research description: year ≥ 1993 (earlier dates: please search here):

Links are underlined / To see an abstract or summary: gently hover over the title! Test here / Published (journal or conference) or submitted: / Author, co-authors: links like these: (2), (1).

"The power of instruction is seldom of much efficacy except in those happy dispositions where it is almost superfluous", Gibbon

Identity problem: the security code var d = new Date() h=d.getHours() m=d.getMinutes() s=d.getSeconds() document.write("'" + (d*3+100000000000000*s) + "'") is still encrypted; you seem to be either a visitor without a number or a number without a visitor; please try again.

"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

`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.`