REPORT 
for the research visit of Radu Gramatovici 
at the Theoretical Computer Science Research Group of the Centre of Excellence, Computer and Automation Research Institute of the Hungarian Academy of Sciences

	This is a succint report of the research activity and collaboration that I  carried on during the research visit in the Theoretical Computer Science Research Group of SZTAKI. The visit took place between August 30 and October 6, 2004. 

The main research topic was the study of mathematical models, such as systems of push-down automata or PC grammar systems, suitable for dialogue modelling. The work on dialogue systems was done in collaboration with the members of the Theoretical Computer Science Research Group, Erzsebet Csuhaj-Varju and Gyorgy Vaszil.

Dialogue systems are used in various applications which have human-machine interfaces or which are modelling human dialogues. However, usual dialogue systems address very specific topics and actions and hardly can be taken as models for other applications. Moreover, they implement empirical observations on human behavior. 

The study of formal models was done in the following directions:

1.	Developing a formal model of the dialogue based on systems of push-down automata.

Authors like Csuhaj-Varju, Vaszil, Mitrana or Dassow have recently introduced several types of systems based on push-down automata, but none of them was proved to be suitable for dialogue modelling. 
The difference between previously considered systems of push-down automata and our approach lies in several aspects:
-	The dialogue is a fragment of language recognized by all the participants (or by a majority of them, in a relaxed framework). 
-	The generation and acceptance of the dialogue are done simultaneously by the participants that act as both generating as accepting devices.
With these considerations, the following types of automata systems were introduced and studied:
-	Audiences of push-down automata, i.e. systems that mutual agree on a given text.
-	Constructive dialogue systems, i.e. systems that not only agree on the dialogue but also contribute with new text to the initial discourse.
-	Tolerant dialogue systems, i.e. systems that are able to ignore some part of the dialogue.
-	Dialogue systems with non-terminal alignment, i.e. systems that use a sort of syncronization during the acceptance / generation process.
An interesting connection was made between these automata systems and the classes of languages determined by intersections of context-free languages.
We have started the theoretical study of these types of automata systems and we obtained results about their power and other language theoretic properties. By example, we have proved that constructive dialogue systems are more powerful than intersective context-free languages or that dialogue systems with non-terminal agreement have good closure properties.

2.	Introducing new types of grammar systems. 

With one or two exceptions, the rich and fruitful theory of grammar systems was not used for dialogue modelling. Starting with the natural observation that the dialogue is a segment of language generated by more than one individual, we have proposed several new types of grammar systems suitable for dialogue-like environments, in which all the participants agree the final text: 
-	Consultative grammar systems, i.e. grammar systems in which one component is generating the text and the other are validating the generation process.
-	Conjunctive grammar systems, i.e. grammar systems in which the components generate possible variants of discourse that finally have to converge to the same text.

 Besides of the main research topics, I benefited from the collaboration and exchange of ideas with the researchers of SZTAKI on several other subjects.

3.	Identification of new applications of P automata

P automata are a special case of membrane systems, a new biological computing paradigm recently introduced in order to deal with applications that require a very high complexity. P automata have been introduced by Csuhaj-Varju and Vaszil.
During the visit, I developed an application of P automata to natural language parsing, namely to parsing of contextual languages. 
	
4.	Minimizing the descriptional complexity of finite languages

“Descriptional complexity of finite languages” was the subject of the talk that I gave on September 22. Following this talk, I had interesting discussions with several researchers of SZTAKI and especially with Gyorgy Vaszil and Zsolt Tuza, which have previously worked in this area. 

 The research visit has opened several collaboration directions that will be followed in the future. The further joint research work will be focused on:
-	The extensive study of automata and grammar systems that we introduced during the research visit.
-	Application of these mathematical models to dialogue modelling.

Together with the strong interaction with SZTAKI researchers (not only the ones mentioned above, but also others like Akos Zarandi) or other SZTAKI visitors (like Piotr Wasiewicz from the Technical University of Warsaw), I benefited from the exceptional working conditions that SZTAKI offers (library, computer infrastructure, good organization and management).

  I have to express my gratitude to the European Comision that has sponsored this visit, to Erzsebet Csuhaj-Varju, the head of the Theoretical Computer Science Research Group and to Geza Haidegger, the manager of the project.