Research Group on Formal Language Theory, Computability and Cryptography

Activities

Members

Publications

Projects

Links

Call for Papers

We are organizing the 10^th International Colloquium on Grammatical Inference (ICGI 2010)

Research Topics

Formal Languages and Automata Theory
Our research is focused in the Formal Language Theory mainly frameworked in the Chomsky's Hierarchy. We work on closure properties of formal languages, grammatical approaches to characterize new (sub)classes of formal languages and computational devices to define them. Particularly, we are interested in the class of regular languages characterized through the Finite Automata Theory. We work on the study between the relations of deterministic and non-deterministic finite automata, structural characterizations of classes of regular languages, descriptional complexity of regular languages and their relationship to grammatical inference. In addition, we work in semigroup theory applied to formal language theory, particularly we study positive varietes and other characterizations of regular languages through an algebraic approach.


Publications

Natural Computing
Our research is focused in the areas of natural computing inspired by biochemical and biocellular processes. This is also a part of what is called unconventional computation. We are interested in the computation models induced by DNA, RNA and protein processes (such as recombination, complementarity, replication through PCR, etc.) With respect to biocellular processes we work on Membrane Computing (P systems), Networks of Biologically-Inspired Processors and other related models. In addition, we are interested in the relationship between these new models of computation and other areas of natural computing such as evolutionary computing.


Publications
Seminar on Formal Language Theory and Biomolecular/Biocellular Computing


Processing of biosequences
Our research is focused in the design of efficient algorithms to solve problems related to the analysis and prediction in biosequences. We mainly work on sequences of nuclueotides for DNA/RNA in order to solve problems such as multiple alignment, functional prediction, and gene expressions, among others. We also work on sequences of aminoacids for proteins in order to solve problems such as motif prediction and secondary structure prediction, among others. We usually apply Grammatical Inference techniques in order to build efficient models to carry out the previously referred tasks. In addition, we work on grammar construction and kernel methods to achieve some of our goals.


Publications
Web server for protein structure prediction
Software downloads


Grammatical Inference and Applications
Our research is focused in the design and the study of efficient grammatical inference methods. We work in the framework of Gold's Identification in the Limit. We characterize new language classes under the learnability criterium and we study the properties of the hypothesis representations such as finite automata or formal grammars. We study the performance of the proposed grammatical inference algorithms with respect to the time and space complexities. Our methods have been succesfully applied in different tasks such as OCR, speech recognition, dialogue modelling, machine translation and biosequences processing.


Publications
10^th International Colloquium on Grammatical Inference (ICGI 2010)

Interactive Proof Systems, Complexity and Cryptography
Our research is focused in the design of algorithms for symmetric and public-key cryptography and the design of protocols for authentication and other ways of providing privacy. We study different aspects of formal language theory in order to be applied to cryptography. In addition we study interactive proof systems as a way of characterizing complexity classes and zero-knowledge protocols.


Publications