Objectives & Achievements

This part of the report will allow you to describe the way in which the Unit is organized and managed, to give the general objectives of the research within the Unit and finally to give a brief description of the main achievements of the research carried out in the Unit as a whole during the 2007 period. A maximum number of characters (without spaces) is allowed in each field. If the number of characters exceeds the maximum you will not be able to complete the form and an error message will appear when you try to save your work.

1. Unit Description (2000 ca.)
Here indicate form of organization and management.

The Laboratory of Artificial Intelligence and Computer Science (LIACC) at the University of Porto was organized since its creation in 1988 (5 PhDs) as a federation of 3 groups that initially shared a common interest in Logic Programming and that were formed by researchers from 3 Faculties: Science, Economics and Engineering. This model proved to be quite adequate until 2007 (39 PhDs) when, after hearing the Advisory Board, a reorganization took place leading to 4 thematic research groups, working in collaboration on a few long-term research goals.

This reorganization created the opportunity for a definition of new long-term objectives, selected by their relation to hard real-world problems posed by the use of computers, and for increasing the cohesion of LIACC as a whole by linking these objectives to the short-term objectives of the research groups.

The management of LIACC is done according to the FCT Multi-year Funding Program rules, through a Coordinating Board, a Scientific Council and an external Advisory Board. The Coordinating Board is composed by three senior researchers, one of which is the LIACC Coordinator, and three researchers usually elected among the heads of the research groups. The Scientific Council, responsible for the approval of annual reports and plans, is composed by all the researchers holding a PhD. LIACC activities are periodically reviewed by an Advisory Board whose members are invited among internationally recognized outstanding experts.

Until December 2009 the following researchers will be in charge:

- LIACC Coordinator: Eugénio Oliveira

- LIACC Coordinating Board: Eugénio Oliveira, Luís Damas, Miguel Filgueiras, Armando Matos, Ana Paula Tomás, Luís Paulo Reis

- Advisory Board: Claude Kirchner (INRIA, France), Carles Sierra (IIA, CSIC, Barcelona), and new member to be confirmed

2. General Objectives (3000 ca.)
This refers to the current aims of the Unit as a whole.

LIACC aims at helping to solve the following general problems:

- Software reliability

Reliable software is still the main challenge in computer science; software engineering approaches failed in general; formal approaches based on logic specifications and theorem proving have trouble handling real programs with a loose specification; unit tests improve the reliability of parts of the program but fail to guarantee reliability of the whole; design by contract approaches (e.g. ruby, spec-#) combined with type inference can improve reliability but do not guarantee correctness; may be a combination of different approaches should be used.

- Distributed, Dynamic and Decentralized problems

There are classes of problems that are inherently of a distributed, dynamic and decentralized nature as those which occur when heterogeneous partners need to collaborate over a computer network. Such a class comprises Electronic Institution problems related to services like negotiation mediation, ontology mapping, contract drafting, contract monitoring and enforcement, and evaluation of reputation values for Virtual Enterprises life-cycle automatic assistance. These problems are better addressed through Autonomous Agents and Multi-Agent Systems (MAS). However improvements are required both on the theoretical and practical aspects, in order to achieve better interoperability, decision making, agents- and team- coordination. Approaches to this include the use of Adaptation, joint Learning capabilities, Emotion-like architectures for cognitive agents, agent-based simulation platforms. Direct application areas are Electronic Institutions problems and Intelligent Text Mining.

- Security

Security of software and of communication is currently a major concern. Public key cryptography techniques are based on the computational intractability of the associated code breaking problem. However this is normally judged on worst case complexity and better measures of security are needed. One possible approach is the use of time bounded versions of Kolmogorov complexity. Another problem arises from the need to execute foreign code that may open the door to attacks. One solution is to force foreign code to include a proof that it will not break security. This however requires support for the development of proofs of program properties.

- Information processing reliability

Representation of information is a major problem of computer science. Coherence and reliability of information is still almost completely left to programmers; e.g. information migration between representations is done without enforcing any kind of reversibility and can lead to loss of information; standards like XML ignore this kind of problem. There is a strong need for models (e.g. like reversible languages) and tools to achieve reliability in information processing.

3. Main Achievements during the year of 2007 (3000 ca.)
Highlights from past research over the period under evaluation.

Collaborative work across LIACC research groups on emotion-like BDI agents architecture and logic-based formalization and for traffic management simulation

* DIVERT, a state-of-the-art traffic simulator, for large scale V2V networks, used for studying critical parameters of vehicular adhoc networks. A spin-off, GeoLink, was created

* Multi-Agent System for a real application on Operations control recovery for crew and plane scheduling (with TAP)

* Monomorphic version of system L and a study of the polymorphic version; a decidable type system for L. Definition of linear recursive functions equivalent to the computable functions; a proof of minimality of the call-by-need strategy for L

* New technique based on Algorithmic Information Theory for automatic classification of fetal heart rate records

* Integration of multiple agent-based services, including Electronic Contracting in a Electronic Institution Platform for Virtual Enterprises Life Cycle

* Characterization of the principal types of BCK-lambda-terms, i.e. theorems of condensed BCK-logic

* Canonical form for minimal acyclic deterministic finite automata

* Strategic Layer for Multi-Agent Teams used for different scenarios with very good results (with IEETA/Aveiro U.): Simulation League 3D (European Champion 2007); Simulation League 2D (2nd Place European contest 2007); PV-League (2nd place in World contest).

* Spatial-Yap, extending the Yap Prolog system and the MYDDAS interface to handle vectorial spatial data. It improves spatial data handling in all aspects

* Semantics for lazy evaluation with appropriate cost information and a version of a type system for deriving cost information for lazy programs

* Logic-based formalization of An Emotion-like BDI agent architecture has been proposed

* Enumeration formula of Serial-Parallel graphs

* New regular expressions equivalence test

* VeriFlog was extended with the ability to repair the web-pages that do not obey to a given rule, based on compile time and run-time type-checking

* New implementation of our solver for Minimum Vertex-guard Problems, for orthogonal polygons with or without holes, distinct partitions and visibility ranges

* Compiler for the F# programming language; development of Condorcert Voting Method system using the B method; PCSC for OCaml, a middleware for programming smart cards

* Full automated cipher-text-only cryptanalysis attack

* Two variants of "depth" unified and related to the "randomness deficiency". A relationship betwen Kolmogorov complexity and constructive Hausdorff dimension of infinite strings was found

* Relationship between between two notions of computational entropy based on the time bounded version of Kolmogorov Complexity

* JEDI Project proposal, ranked excellent in 26 out of 230 submissions to FCT 2006 CSc call

* RAPOSA question answering system for Portuguese ranked 3rd in the international contest QA@CLEF 2007


This part of the report will allow you to describe general activities of the Unit that are aimed at integrating the research of various groups of which multidisciplinary and/or trans-disciplinary activities are of particular relevance. The second part is aimed to describe work that the Unit does to extend beyond the scientific environment and to reach the general public, schools or other forms of engaging the public in the work of the Unit.

1. Integrative/multidisciplinary activities during the year of 2007 (3000 ca.)
Special activities that aim to carry out research across disciplines.

- Research Units in other disciplines with which there were joint projects:

Google Labs [Text information extraction and retrieval]

University of Amsterdam (UvA), ILPS Group [Information and Language Processing Systems]

CEMAS, Porto [Environmental systems, Agent-based simulation]

ISR, Porto [Hardware, Automated guided vehicles]

Universidade de Coimbra, Faculdade de Psicologia e Ciências da Educação [Handling of structured documents]

Universidade do Porto, Faculdade de Letras [Handling of structured documents]

Universidade do Porto, Faculdade de Medicina [Medical Informatics]

Universidade do Porto, Faculdade de Psicologia e Ciências da Educação [Handling of structured documents]

2. Outreach activities during the year of 2007 (3000 ca.)
Science and Society/general public/schools, etc.

- spin-off company


- links with other public-sector and industrial partners

Intevation Gmbh

Parque Natural da Ria Formosa

TAP - Transportes Areos Portugueses

- systems for disabled people

wheelchair with intelligent control, under development

translator from mathematical expressions in LaTeX into Braille, Portuguese variant; prototype available

- software with wide distribution

Apoo: an Environment for a First Course in Assembly Language Programming, 1998-2004. Linux Debian and Ubuntu distributions

GPSMan: a graphical manager of GPS data, 1998-2007, Linux Debian and Ubuntu distributions, FreeBSD Unix distribution, and GIS-Knoppix and AI9NL Linux Live-CDs; part of the Free-GIS CD

Yap: state-of-the-art Prolog implementation with support for constraints, tabling, parallelism, external data-bases, and spatial data-bases. Available from Sourceforge

- collaboration in postgraduate actions

Doctoral PhD Programmes on:

-- Informatics Engineering, University of Porto

-- Computer Science, University of Porto

-- Informatics (MAPI), Universities of Aveiro, Minho and Porto

-- Telecommunications (MAPTele), Universities of Aveiro, Minho and Porto

Master of Science Programmes on:

-- Computer Science

-- Informatics Engineering

- collaboration in other training actions:

supervision of EU-Socrates scholarship holders

- science dissemination

collaboration with Atractor, an association for the diffusion of Mathematics, in the development of interactive modules

several seminars on AI and Intelligent Robotics given at high-schools

General Indicators

This section is a simple summary table describing the total number of PhD researchers within the Unit along time, as well as the total number of completed Masters and PhDs during the year of 2007

Nº of Researchers (FTE)*
Masters Completed in the Period
PhDs Completed in the Period
* Full Time equivalent researcher refer exclusively to PhDs. 1PhD with equal of more than 20% dedicated to research in the Unit is equal to 1.0 FTE.

Research Groups

In this last section of the report you have the names of each Research Group and the Principal Investigators that were proposed to the period 2007-2010 period. You have to confirm whether the Group was part of the Unit during 2007 or insert the Research Groups that made up the unit, if they are not present on this list. Once the table is completed each individual Research Group can start filling in their individual form by pressing on the group’s name.

By following the link in the groups name you will be able to access the individual form of the group.
To remove a given group you need to select the checkbox and press "-REMOVE"(4).

Group:Principal Investigator
Distributed AI and Robotics Group
Eugenio da Costa Oliveira
Formal Models of Computation
Sabine Babette Broda
Advanced Programming Systems
Ana Paula Nunes Gomes Tomás
Language, Complexity and Cryptography
Armando Barbot Campos Matos