- Complexity (Kolmogorov, Communication, Instance): properties of certain measures of information such as computational depth, which may be characterized as a difference between two measures of complexity; analysis of cryptographic protocols using new measures of information; clustering methods for medical data based on Kolmogorov Complexity.

- Reversible Computations: models and their properties.

- Logics for multi-agent systems: logical frameworks for reasoning about the role of Artificial Emotions in the Belief-Desire-Intention agent architecture.

- Combinatorics and algorithmic graph theory: combinatorial games and graph problems, namely the study of the combinatorial number h(n) and of generation methods for polyominoes.

- Formal Languages: characterization of equivalent models for regular languages and of the algorithms to convert between them regular languages.

- Cryptology and Security of Protocols: automated cryptanalysis attacks of classical symmetric ciphers; digital reconstruction of cryptanalysis methods developed in the mid-20th century; proprieties of modern security protocols using symmetric and public-key cryptography.

A new technique based on Algorithmic Information Theory for the automatic classification (without domain knowledge) of the fetal heart rate records. Fetal heart rate monitoring is commonly used to detect abnormal situations where the life of the fetuses may be endangered; the new technique correctly clustered together and detected all the abnormal or suspicious tracings in an experiment with 31 fetuses.

A novel method of measuring the individual security of cryptographic protocols (with external collaboration). The absolute security of protocols using symmetric keys has been studied. This is an alternative to the usual statistical methods.

A unique string representation for complete initially-connected deterministic finite automata. It was shown to be adequate for exact and uniform random generation, providing an alternative way of counting and an optimal coding. Both exact and approximate values for the number of regular languages and density of minimal automata were obtained with an impact in studies of average-case complexity.

A language whose programs correspond to reversible transformations of tuples of integers. It characterizes a fundamental and powerful set of reversible transformations whose properties are being studied. This is similar to the characterization of primitive recursive functions by a simple programming language (LOOP).

L. Antunes, L. Fortnow, D. van Melkebeek, and N. Vinodchandran, Computational Depth: Concept and Applications. Theoretical Computer Science, 354 (3), 391-404, 2006. IF=0.843, nC=1

Armando B. Matos, Linear programs in a simple reversible language. Theoretical Computer Science, 290(3), 2063-2074, 2003. IF=0.843, nC=1

L . Antunes and L. Fortnow, Sophistication revisited. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 2719, 267-277, Springer-Verlag, 2003. IF=0.402, nC=1

Peter Blanchard, Frank Harary and Rogério Reis, Partitions into sum-free sets. INTEGERS: The Electronic Journal of Combinatorial Number Theory, 6, A7, 2006.

Nelma Moreira and Rogério Reis, On the density of languages representing finite set partitions. Journal of Integer Sequences, 8, 2005.

L. Antunes, L. Fortnow, and V. Vinodchandran, Using depth to capture average-case complexity. In 14th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science 2751, 303-310, Springer-Verlag, 2003. IF=0.402, nC=0

C. Costa-Santos, J. Bernardes, P. Vitányi, and L. Antunes, Clustering Fetal Heart Rate Tracings by Compression. Special Track on Data Mining, the 19th IEEE International Symposium on Computer-Based Medical Systems, 2006.

* MSc

Manuel António Ferreira, Using Kolmogorov Complexity on the analysis of interactive protocols. 2006

José João Gonçalves Morais, Computing Small Regular Expressions from Finite Automata. 2005

Liliana Salvador, Perfect Secrecy of Symmetric Ciphers. 2005

Lance Fortnow CS University of Chicago

Dieter VanMelkebeek CS University of Wisconsin

Sophie Laplante LRI-University of Paris-Sud

Paul Vitányi CWI-University of Amsterdam

Peter Blanchard, Miami University

Frank Harary, Distinguished Professor of Computer Science, New Mexico State University

Relation to long term objectives denoted by

[SEC] Security

[RI] Reliable Information

1)- Descriptional complexity of regular languages, [SEC,RI]

Due to novel applications in Computer Science - from bio-informatics

to computer networks and Web technologies - automata theory has

faced renewed theoretical developments. The main objectives of this

line of research are

- Study of the non injective and non complexity preserving conversions

between combinatorial representations with the same expressive power

and the descriptional complexity of generic languages operations.

- Enumerative and random generation of languages representations with

applications in characterization studies and average case analysis.

- Development of tools for assisting research on formal and

computational models; due to its combinatorial nature,

high-performance implementations are required. These tools will

include: an open source extensible high-performance software library

for the symbolic manipulation of automata, tools for automatic drawing

of automata diagrams and a modular graphical user interface for the

manipulation of automata and other models of computation.

2) individual analysis of cryptographic protocols, [SEC]

The classical analysis of cryptographic protocols assumes that

certain probability distributions are well defined and known in

advance; but that is often not the case. A completely different

approach is the "individual analysis". Only very recently has this

kind of analysis been attempted. The continuation of the research

(which began a few years ago in LIACC and elsewhere) is the main topic

of this project.

The individual analysis is based on variants of the Kolmogorov

complexity; however, security measures based on resourced unbounded

Kolmogorov complexity are usually uncomputable and defined "apart from

a constant"; this is a serious drawback for practical applications, so

that the research will include the search for appropriate computable

alternatives to Kolmogorov complexity.

3) Formal models for reversible computation; measuring the degree of

reversibility, [RI]

The Landauer principle is the ultimate lower bound for non reversible

computations. Only reversible forms of computation can in theory be almost

dissipationless. The objectives can be divided in 3 main sub-areas

- Characterization and study of very simple reversible languages; this

is the continuation of some previous work in this area.

- Use of Kolmogorov complexity (or related concepts) to measure

the degree of irreversibility of a computation.

- Compare several theoretical models for reversible computation; these

models may include reversible automata, reversible languages, some

forms of rewrite rules and the unitary transformations of quantum

mechanics.

- Search for efficient methods for restoring previous states - such as

previous configurations of a machine or previous states of a database

system).

FCT:

19600 Plurianual 2007

1. Peter Blanchard, Frank Harary and Rogério Reis,

Partitions into sum-free sets.

INTEGERS: The Electronic Journal of Combinatorial

Number Theory, 6, A7, 2006.

2. Marco Almeida, Nelma Moreira, and Rogério Reis,

Enumeration and Generation with a String Automata Representation,

accepted for publication in

Theoretical Computer Science,

special issue "Selected Papers of DCFS 2006".

3. C. Costa-Santos C, J. Bernardes, P. Vitányi, and Antunes L.,

Clustering Fetal Heart Rate Tracings by Compression,

19th IEEE International Symposium on Computer-Based Medical

Systems, 2006.

4. Armando B. Matos,

Linear programs in a simple reversible language,

Theoretical Computer Science, Vol. 290 No. 3,

2003.

5. Alexandre Pinto, André Souto, A. Matos and L. Antunes,

Commitment and Authentication Systems,

Proc. International Conference on Information Theoretic Security,

Lecture Notes in Computer Science,

Springer, 2007 (to appear).

Scholarships for post-grad (MSC and PhD) students