Project: Algebraic and Syntactic Methods in Computer Science (ASMICS 2)
ASMICS 2 is the continuation of the Working Group ASMICS established in September 1989. Its aim is to bring together a community of researchers to collaborate on problems in algebraic and syntactic methods in computer science. Topics include automata and grammar theory, semigroup theory, combinatorics on words and theory of codes, concurrency theory, trace theory, infinite behaviour of programs and parallel computations.
This research is not a priori linked with any specific application. However results in these theories have proved recently to be of interest in the following domains: speech and natural language, concurrent and real time programming, algorithms for parallelism and distributed models of computation, logic programming, databases, knowledge engineering and representation. It is hoped that some basic results will enrich the core of computer science concepts which are taught to computer professionals.
1. Objectives
1.1 Description of Technical Tasks
The aim of the working group ASMICS 2 is to bring together a community of researchers from various parts of Europe to collaborate on problems in algebraic and syntactic methods in computer science. Indeed the need for research and progress in the area of "mathematical tools for computer science" is widely and deeply felt by all those who are involved in the design and realization of all sorts of computer systems as well as by those who are in charge of educating the future high level computer engineers that are desperately needed in this field.The research undertaken in this project may be divided into four, not disjoint, subareas:
- Formal languages and grammar theory;
- Automata theory (automata on words and trees, finite and infinite computations, automata and semigroup theory);
- Combinatorics on words and theory of codes;
- Concurrency theory, trace theory, infinite behaviour of programs and parallel computations.
The aim of the working group is to support a lively scientific activity in a domain of theory that can offer a conceptually manageable formalism for a broad range of applications. The results frequently provide illuminating analogies and simplified models for the real application domains.
1.2 Activities
This objective will be pursued by means of cooperation that will take place through specialized workshops, short research stays, a program for scientific visits by young researchers at other partners, a general annual meeting of the partners, and a quick distribution of research results among the partners sites. Another objective is to coordinate the activities of those groups that are involved in the development of program systems which implement procedures originating in thetheoretical work; this software will be available to the scientific community. The project has been made of organizing a final meeting in the form of a collection of tutorials open to the scientific community to present the results obtained by the working group.1.3 Potential
The research work conducted in ASMICS 2 is not a priori linked with any specific application. However the results in these theories have proved recently to be of interest in the following domains:- Theories for concurrency and real time: e.g. trace theory; queue automata for real-time scheduling.
- Algorithms for parallelism and distributed models of computation: e.g. asynchronous automata, time stamps.
- Compilation: e.g. parallel parsing algorithms, tree-transducers for code generators.
- Logics and logic Programming: temporal logics, term rewriting and unification.
- Speech and natural language: e.g. finite-state transducers for fast dictionary look-up; unification grammars for semantics.
- Databases: e.g. modeling nested relations by syntactical mappings.
- Knowledge engineering and representation: e.g. graph grammars for modeling object-oriented programs.
