FCT Relatório Científico 2008 [LABORATÓRIO
DE INTELIGÊNCIA ARTIFICIAL E CIÊNCIA DE COMPUTADORES]
|
Group Description |
|
|
Title of Research
Group: |
(RG-COMP-Norte-Porto-27-1037) |
|
Principal Investigator: |
Armando Barbot Campos Matos |
|
Main Scientific Domain: |
Engenharia
Electrotécnica e Informática |
|
Group Host Institution: |
Universidade
do Porto |
|
Funding, source, dates |
|
|
Funding, source,
dates |
|
|
16326 FCT Plurianual 2008 16100 FCT Project RESCUE
2008 12000 FCT Project ASA 2008 1000 FCT Project Memories of
Work 2008 4000 Univ Porto IPG-118 2008 + salaries of team members,
University of Porto 2008 + grants,
FCT, Gulbenkian, others 2008 |
|
|
Objectives
& Achievements |
|
|
Objectives |
|
|
- Descriptional Complexity
of Regular Languages: * The enumeration of
languages based on their model representations are useful for several
language characterizations, and for random generation and average case
analysis. We aim to characterize normal forms of some specific classes of
automata and infer its enumerative consequences. * Establishment of
relationships between the descriptional complexities of automata and of the
corresponding measures for regular expressions. - Development of
high-performance symbolic manipulation software environments for formal
languages - Study security properties
of modern protocols using symmetric and public-key cryptography. - Development of XML based
tools for the edition, annotation, classification and search of multimedia
documents. - Characterize the
complexity computational depth and the sophistication of infinite strings in
terms of appropriate variants of Kolmogorov complexity. - Study the security of
symmetric key protocols using resource bounded versions of Kolmogorov
complexity. - Study individual
non-deterministic communication complexity in terms of information measures
related to Kolmogorov complexity. |
|
|
Main Achievements |
|
|
- A canonical form for
acyclic deterministic finite automata and an exact enumeration algorithm. - Based on random generators
previously designed by the team members, we implemented a database for random
samples of deterministic and non-deterministic finite automata, as well as,
of regular expressions. - Improvements on the
regular expressions equivalence test by using partial derivatives.
Formalization of this method in terms of the computation of right-invariant
relations. - Development of a graphical
interface and editor for automata manipulation with export/import filters and
a generic interface with external systems. - Development of software
tools for searching linguistic patterns in annotated texts. - Development of a network
simulator for the analysis of the security properties of peer-to-peer
protocols. - Implemented a python
module for elliptic curve arithmetics that permits easy implementations of
Elliptic Curve Cryptography algorithms. - An appropriate definition
of sophistication for infinite sequences was obtained. Based on Baire's
theorem, the density of the lower and upper sophisticated sequences was
analyzed. - The decision problem
associated with the problem of finding the maximum area of a monochromatic
combinatorial rectangle (mcr) of a given colored square was shown to be
NP-complete. Several improvements and generalizations of the results
previously known about asymptotic maximum area of the mcrs of a random square
were established. A new lower bound of the communication complexity of the
random function was obtained. |
|
|
Group Productivity |
|
|
Publications in peer review
Journals |
|
|
Marco Almeida, Nelma Moreira,
and Rogério Reis. Exact
generation of minimal acyclic deterministic finite automata. International
Journal of Foundations of Computer Science, 19(4):751-765, August 2008. David Pereira and Nelma
Moreira. KAT and PHL in COQ. Computer Science and Information Systems,
05(02), December 2008. ISSN: 1820-0214. Also in Corta'08. Accepted for publication: Luis Antunes, Armindo Costa,
Armando B. Matos and Paul Vitanyi. Computational depth of infinite strings
revisited. Theory of Computing Systems. L. Antunes, A. Matos, A.
Souto and P. Vitániy. Depth as randomness deficiency. Theory of Computing
Systems A. Pinto, A. Souto, A. Matos and
L. Antunes. Commitment and Authentication Systems. Designs, Codes & Cryptography
(Springer). |
|
|
Other publications
International |
|
|
Marco Almeida, Nelma
Moreira, and Rogério Reis. Antimirov
and Mosses's rewrite system revisited. In O. Ibarra and B. Ravikumar,
editors, CIAA 2008: Thirteenth International Conference on Implementation and
Application of Automata, number 5448 in LNCS, pages 46-56. Springer-Verlag,
2008. David Pereira, Eugénio Oliveira, and
Nelma Moreira. Formal
modelling of emotions in bdi agents. In F. Sadri and K. Satoh, editors,
Eighth Workshop on Computational Logic in Multi-Agent Systems (CLIMA-VIII),
number 5056 in LNAI, pages 62-81, Porto, Portugal , 2008. Springer-Verlag. Marco Almeida, Nelma
Moreira, and Rogério Reis. Exact generation of acyclic deterministic finite
automata. In Workshop on Descriptional Complexity of Formal Systems (DCFS08),
Charlottetown, Canada, July 2008. Marco Almeida, Nelma
Moreira, and Rogério Reis. On the
performance of automata minimization algorithms. In Arnold Beckmann, Costas
Dimitracopoulos, and Benedikt Löwe, editors, CiE 2008: Abstracts and extended
abstracts of unpublished papers., 2008. L. Antunes & A. Souto.
Sophisticated infinite sequences. In Local Proceedings of CiE (Computability
in Europe) 2008. Athens University, Greece, June 2008 André Almeida, José Alves, Nelma
Moreira, and Rogério Reis. Cgm:
A context-free grammar manipulator. In Corta 08,
Bragança, Portugal, July 2008. |
|
|
Other publications
National |
|
|
António José Machiavelo e
Rogério Reis. Sherlock Holmes
e o Sudoku. Boletim Sociedade Portuguesa de
Matemática, n.59 Outubro 2008 |
|
|
Master and Ph.D. thesis
completed |
|
|
Nosy: a simulator
for network protocols analysis, João Miguel Mendes, Masters
in Informatics , FCUP. 2008 (supervisor: Rogério Reis) |
|
|
Patents/propotypes |
|
|
Apoo, an environment for a
first course in assembly language programming (http://www.ncc.up.pt/Apoo) Yappy,a parser generator for
Python (http://www.ncc.up.pt/Yappy) FAdo,tools for formal
languages manipulation (http://www.ncc.up.pt/FAdo) Guitar, Graphical
environment for editing and automatic drawing diagrams
(http://www.ncc.up.pt/FAdo) nosy: a simulator for
network protocols analysis |
|
|
Internationalization |
|
|
We started new
collaboartions with researchres in Automata Theory and Formal Languages: - University of Manitoba,
Winipeg, Canadá (Michel Domaratzki) - University of Western
Ontario, London, Canadá (Sheng Yu) We continued collaborations
with: - Lance Fortnow (University
of Chicago, now at Northwestern University McCormick School of Engineering) - Paul Vitanyi (CWI,
University of Amsterdam) |
|
|
Future Research |
|
|
Objectives |
|
|
Descriptional Complexity of
Regular Languages: a) Enumeration and Random
Generation - To obtain more compact
normal forms for deterministic finite automata (DFA) based on minimal covers,
and build Boltzmann samplers. - To obtain canonical forms
for classes of non-deterministic finite automata (NFA) and the corresponding
enumeration results. Minimal unary NFA are of special interest because the
their analogies with number theory. b) Succinctness and
Conversions: Conversions between
equivalent regular languages representations are in general non injective and
non complexity preserving. We intend to focus on the conversions from NFA and
regular expressions (RE) and on small NFA characterizations. In both cases we
intend to characterize properties of automata underlying graphs and to define
sets of transformations between the underlying graphs of equivalent automata,
based on algebraic RE equivalences. c) Average case analysis: - To obtain results towards
the average-case analysis of algorithms for regular languages equivalence and
DFA minimization. d) High-performance symbolic
manipulation software - To continue to development
of a set of tools for automata manipulation that allow the easy prototyping
of new algorithms and testing performance in large datasets. - Concerning the graphical
tools, to design and implement tools for automatic drawing of automata
diagrams that respect, as far as possible, common accepted aesthetics
principles. e) Cryptology and security
of Protocols - Public-key cryptosystems
based on number-theory concepts, tend to be computationally expensive. On the
other hand, finite automata based public-key cryptosystems (FPAKS) exhibit
good performance and its keys are relatively small. We intend to study the
feasibility of this approach by defining adequate measures and to study the
security properties of the FPAKS based on those measures. f) Algebraic analysis of
processes and algorithms of classical symmetric ciphers both considering them
as cryptographic devices and as combinatorial objects. Use of information measures
based on Kolmogorov complexity to characterize cryptographic protocols - Continue the study the
security of symmetric key protocols using resource bounded versions of
Kolmogorov complexity. - Study individual
communication complexity in terms of information measures related to
Kolmogorov complexity. These activities will be
pursued in the scope of the new Computer Science Group that results from the
merge of the APS, FMC and LCC groups. |
|
|
Funding, source,
dates |
|
|
expected 7533 FCT Plurianual 2009, depends on outcome of pending evaluation 16100 FCT Project RESCUE
2009 2000 FCT Project ASA 2009 Pending funding: "Cante:
descriptional and computational complexiy
of formal languages" submitted to FCT feb.2009 (36 months;
budget 196K euros) "Moloch: Memories of labour Linguistic Corpus" submitted to FCT feb.2009 (36 months; budget
145K euros) |
|