Group DescriptionPlease confirm here the name of the group, the Host Institution in which the Principal Investigator is located, four Key words that best describe your work and finally in concise form indicate mains sources of funding for the research of your group. Include all types of funding, like FCT projects, FCT Base, as well as funding from other institutions. You should indicate an approximate amount in EUROS, and the source to which the funds apply. |
| 1. Group Name/Designation |
Language, Complexity and Cryptography (RG-COMP-Norte-Porto-27-1037) |
| 2. Principal Investigator |
| armando barbot campos matos |
| 3. Location of Group (Host Institution) |
| Universidade do Porto |
| 4. Keywords |
| | | | |
| 5. Funding, source, dates (1000 ca.) |
31373 FCT Plurianual 2007
32500 FCT Project KCrypt 2007-2008
24000 FCT Project ASA 2007-2009 [prime contractor CMUP]
22500 FCT Project "Memories of Work" 2007-2009 [prime contractor FPCEUP]
4000 University of Porto Project IPG 118
+ salaries of team members, University of Porto 2007 + grants, FCT, Gulbenkian, others 2007
|
PI & ResearchersIn this section indicate first the PhD researchers that make up the group by selecting them from the list of researchers integrated in the Unit. In the second section you can indicate whether other PhD researchers not integrated in the Unit collaborate with group by typing their public key. Finally in the last part you should include all the non-PhDs members of the group. |
|||||
| 1. Researchers in the Group (PhD. Only) (1) | |||||
|
|||||
| 2. Other Researchers in the Group (PhD.) (2) | |||||
|
|||||
| 3. Other Researchers in the Group (non PhD.) (2) | |||||
|
|||||
Objectives & AchievementsIn this section please describe the main objectives and achievements of the group during the 2007 period . If the number of characters is more than the permitted maximum you will not be able to complete the form. |
| 1. Objectives (2000 ca.) |
- Descriptional Complexity of Regular Languages: the enumeration of languages based on their model representations are useful for several language characterization, and for random generation and average case analysis. We aim to characterize the normal forms of some specific classes of automata and infer its enumerative consequences. We also aim to explore the possible relationships between the descriptional complexities of automata and of the corresponding measures for regular expressions.
- Cryptanalysis of classical ciphers: we are interested in the algebraic analysis of processes and classical algorithms both considering them as crytographical devices and as combinatorial objects.
- To obtain a Kolmogorov based characterization of certain information properties like computational depth and sophistication) of infinite strings.
- To characterize the individual instances of unconditionally secure cryptographic protocols and use resource bounded versions of Kolmogorov complexity to study the security of symetric key protocols.
- The classic concept of entropy is entirely based on probability theory, ignoring the difficulty of the computations involved; relate previous attempts to define a computational entropy, possibly using some resource bounded version of Kolmogorov complexity.
|
| 2. Main Achievements (2000 ca.) |
- A new technique based on Algorithmic Information Theory for the automatic classification (without domain knowledge) of the fetal heart rate records (work started in 2006).
- A canonical form for minimal acyclic deterministic finite automata was developed, which provided for the first time in the literature the exact enumeration of this kind of automata.
- A recursive formula for the enumeration of Serie-Parallel graphs (and automata) and a generation algorithm.
- Experimental results on the comparison of several finite automata minimization algorithms led to new conjectures about their average-case complexity.
- A new regular expressions equivalence test based on rewriting was implemented. Experimental results suggest better average-case than classical methods.
- A full automated cipher-text-only cryptanalysis attack was developed and implemented.
- Analysed and studied the plausibility of the polish cryptanalysis attacks to the Enigma cipher.
- An XML based document editor for the classification and annotation of semistructed documents that allows the definition of category hierarchies
- Two variants of "depth" (logical depth and computational depth) have been unified and related to the notion of "randomness deficiency" (Kolmogorov and Levin). Several properties of infinite strings have been studied and related, namely the (normalized) Kolmogorov complexity and the constructive Hausdorff dimension.
- The time bounded version of Kolmogorov Complexity has been used to establish relations between two notions of computational entropy (one from Yao and the other from Implagliazzo, Levin and Luby).
- An unexpected relationship between non-deterministic computational complexity and the resource unbounded version of instance complexity has been discovered and studied.
- Continuation of the study of the characterization of the individual instances of unconditionally secure cryptographic protocols. |
ProductivityThis section refers to the research output of the group during the 2007. From the list provided choose the items that you want to complete and a field will appear. Follow the instructions provided in each item. You are not required to fill in all the items only those for which your group has output. Please note that for peer reviewed publication you must include impact factor and number of citations. If these indicators are not available you must include that publication as Other Publications. |
| Publications in peer review Journals (3000 ca.) (Up to a max of 10. Always indicate at the end of the citation, impact factor of the journal (IF=) and number of citations (nº C=). Give title and full citation in original language. DO NOT translate) |
Luís Antunes and Lance Fortnow Sophistication Revisited Theory of Computing Systems, DOI10.1007/s00224-007-9095-5 Published: November 2007 IF=0.769 nºC=0
Marco Almeida, Nelma Moreira, and Rogério Reis. Enumeration and Generation with a String Automata Representation. Theoretical Computer Science, special issue "Selected papers of DCFS 2006", vol. 387 n. 2, pp. 93-102. 2007 IF=0.843 nºC=1
|
| Other publications International (3000 ca.) (Include only Books, chapters or full papers published in conference proceedings up to max of 10. Give title and full citation in original language) |
António Machiavello and Rogério Reis. Automated Ciphertext-Only Cryptanalysis of the Bifid Cipher. Journal of Cryptologia (indexed journal), vol 31 n.2, pp 112--124, April 2007. Indexed journal, nº C=0
Luis Antunes, Armindo Costa, Armando Matos and Paul Vitanyi, Computational Depth of Infinite Strings Revisited, CiE 2007, 2007.
A. Ferreira et. al. Why facilitate patient access to medical records. Proc. International Council on Medical & Care Compunetics, 2007.
A. Ferreira, R. Cruz Correia, L. Antunes, D. Chadwick. Access Control: how can it improve patients' healthcare? Proc. International Council on Medical & Care Compunetics, 2007.
Marco Almeida, Nelma Moreira, and Rogério Reis. Exact generation of minimal acyclic deterministic finite automata. Proceedings of the 9th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS07),pag. 58--68, High Tatras, Slovakia, 2007.
A. Pinto, Comparing Notions of Computational Entropy, Computation and Logic in the RealWorld, third Conference on Computability in Europe CiE 2007, Siena, Italy, Springer Lecture Notes in Computer Science, volume 4497 2007
L. Antunes, L. Fortnow, A. Pinto, and A. Souto Low-depth Witnesses are Easy to Find 22nd Annual IEEE Conference on Computational Complexity, San Diego, US, pp 46-61, 2007
A. Pinto, A. Souto, A. Matos, and L. Antunes Commitment and Authentication Systems Second International Conference on Information Theoretic Security, Madrid, Spain, May 2007. Proceedings of the 2nd International Conference on Information Theoretical Security Yvo Desmedt (ed), pp 3-23, 2007
L. Antunes, S. Laplante, A. Pinto, and L. Salvador Cryptographic Security of Individual Instances Second International Conference on Information Theoretic Security, Madrid, Spain, May 2007. Proceedings of the 2nd International Conference on Information Theoretical Security, Yvo Desmedt (ed), pp 205-220, 2007
Armando B. Matos, Andreia C. Teixeira and André C. Souto, Non-deterministic Communication Complexity and Instance Complexity, Computational and Logic in the Real World CiE, Siena 2007, Barry Cooper, Thomas Kent, Benedikt Lowe and Andrea Sorbi (eds), pág~274-282, 2007
Silvestre Lacerda, Norberto Lopes, Nelma Moreira, Rogério Reis. Ferramentas para a Construção de Arquivos Digitais de História Oral. Actas XATA 2007, XML: aplicações e tecnologias associadas. J. Ramalho, J. C. Lopes e L. Carriço (eds.). Universidade de Lisboa, ISBN 978-972-99166-4-9, 2007.
|
| Master and Ph.D. thesis completed (3000 ca.) |
PhD Thesis: Rogério Reis, Autómatos finitos: manipulação, geração e contagem, PhD, FCUP, 2007.
Msc Thesis: Andreia C. Teixeira, "Complexidade de Comunicação: Relação com o Tamanho dos Rectângulos e com a Complexidade das Instâncias", Msc in Informatics, DCC-FCUP, 2007.
Msc Thesis: B. Ribeiro. The Enigma cryptanalysis: 1932-1939. Msc in Informatics, DCC-FCUP, 2007.
|
| Patents/propotypes (2000 ca.) |
PROTOTYPES
FAdo: software library for automata and regular expressions manipulation.
Klass: An XML based document editor for the classification and annotation of semistructed documents that allows the definition of category hierarchies.
|
| Internationalization (2000 ca.) (Collaborative publication, Research, Graduate Training Networks or other forms of participation of the Research Group at the international level) |
The following actions resulted in several submitted papers (two of them already published)
- Research collaboration with Sophie Laplante, LRI, Laboratoire de Recherche en Informatique Université Paris-Sud, France
- Research collaboration with Lance Fortnow Department of Electrical Engineering and Computer Science Northwestern University McCormick School of Engineering, USA
- Research collaboration with Paul Vitányi and with Harry Buhrman Algorithms and Complexity research group CWI, Centrum Wiskunde & Informatica, the Neederlands |