<=<=
<=<=
<=<=
<=<=
<=
<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<= <=
<=

<=

<=

<=
<=

<=

<=

<=
<=

<=

<=

<=
<= <=
<=

<=
<= <=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

Universität Stuttgart

Fakultät Informatik

?

Institut für Informatik

Breitwiesenstraße 20-22

D-70565 Stuttgart

Workshop on

Formal Languages, Automata and

Petri-Nets

Holger Petersen

(Editor)

Report Nr. 1998/01

January 1998

Seite 1998: nächste Seite | Übersicht

Seite 1999: vorherige Seite | nächste Seite | Übersicht

Foreword

This report contains abstracts of the lectures presented at the workshop \Formal Languages, Automata and Petri-Nets" held at the University of Stuttgart on January 16{17, 1998. The workshop brought together partners of the German-Hungarian project No. 233.6, Forschungszentrum Karlsruhe, Germany, and No. D/102, T?eT Foundation, Budapest, Hungary. It provided an opportunity to present work supported by this project as well as related topics.

The editor wishes to thank the University of Stuttgart and the \Vereinigung von Freunden der Universität Stuttgart e.V." for support which made the participation of the Hungarian colleagues possible. Thanks are also due to the speakers for their contributions and to the members of the group \Theoretische Informatik" for their assistance.

Stuttgart, January 1998 Holger Petersen

Workshop 1 Stuttgart, January 1998

Seite 1: vorherige Seite | nächste Seite | Übersicht

Speakers

Henning Bordihn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Erzs?ebet Csuhaj-Varj?u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Volker Diekert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Henning Fernau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Alfons Geser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

S?andor Horv?ath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

L?aszl?o K?aszonyi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Manfred Kudlek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Klaus-Jörn Lange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Markus Lohrey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Anca Muscholl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Klaus Reinhardt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

György Vaszil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Workshop 2 Stuttgart, January 1998

Seite 2: vorherige Seite | nächste Seite | Übersicht

Cooperating/Distributed Grammar Systems {

Various Different Points of View

Henning Bordihn

Institut für Wissens- und Sprachverarbeitung

Otto-von-Guericke-Universität

Universitätsplatz 2, 39106 Magdeburg

Cooperating/distributed grammar systems (CD grammar systems, for short) have been introduced by E. Csuhaj-Varj?u and J. Dassow in 1988 for describing multi-agent systems by means of formal grammars and languages, based on blackboard architectures. A CD grammar system consists of a finite set of grammars that cooperate in deriving words of a common language, where the grammars work on the sentential form in turns according to some cooperation protocol (the mode of derivation).

By the original motivation, competence and completeness of the agents are important features that influence the behaviour of blackboard-type problem solving systems which can be formalized and interpreted in the syntactic framework provided by CD grammar systems. Moreover, they can form a basis of the cooperation protocol. We compare several formalizations of these concepts, mainly variants of the well-known competence-based t-mode of derivation, concerning the induced derivational power. The results are given for both forward deduction systems with generating and backward deduction systems with accepting (analyzing) context-free grammar components.

We note that grammar systems with a cooperation strategy based on the concept of completeness / incompleteness of the components had already been considered by R. Meersman and G. Rozenberg in 1978, as a generalization of two-level substitution grammars to a multi-level approach.

Another point of view is given by seeing CD grammar systems working in t-mode of derivation as a sequential analogue of extended tabled Lindenmayer (ET0L) systems (as context-free grammars can be seen as sequential counterpart of extended non-tabled L systems). We consider CD grammar systems which correspond to the usual variants of ET0L systems, in particular we define CD grammar systems with pure context-free components and we order the generated language classes in an almost complete hierarchy. Furthermore, the influence of restrictions in the number of components is studied.

Workshop 3 Stuttgart, January 1998

Seite 3: vorherige Seite | nächste Seite | Übersicht

Networks of Language Processors

Erzs?ebet Csuhaj-Varj?u

Computer and Automation Research Institute

Hungarian Academy of Sciences

Kende u. 13-17, H-1111 Budapest, Hungary

email: csuhaj@sztaki.hu

Networks of language processors is a collective term ([6]) introduced as a formal language theoretic framework for describing several architectures for highly (massively) parallel and distributed symbolic processing. The notion is strongly motivated by some recent models and paradigms ([8], [14], [15], [12], [3], [4], [2], [10], [9], [5]). There are a lot of arguments for formulating such a concept: among other things, the need for reliable language theoretic support of communication networks, understanding the nature of massively parallel and distributed architectures, including ones with biological or other nature-motivated background.

A network of language processors (an NLP system) consists of several language identifying devices (or mechanisms computing multisets of strings), called language processors, which are located at the nodes of a (virtual) network. The language processors operate on strings (on sets of strings or multisets of strings) by performing rewriting steps and communication steps, usually alternately. The strings can represent data and/or programs (the latter ones correspond to operations in coded form or sets of rewriting rules). Both kinds of them can be rewritten and communicated among the nodes, providing dynamism and introducing adaptation and evolution in the mechanism. The same string can be interpreted at different nodes in different manners: it can play the role of a piece of data at some node and the role of a rewriting rule at some another one. Moreover, creation of new nodes and deletion of existing ones is allowed, mainly as a result of communication, leading to a flexible, self-organizing topology of the network.

At the beginning, each node of the network is initialized by a language processor and a set (multiset) of data strings which, together, form the initial configuration (initial state) of the system. The network is functioning by changing its configurations (this term is used in the case when rewriting rules are communicated) or its states (when only strings representing data are transmitted). The change of the configuration (state) can take place either by a rewriting step or by a communication step. By a rewriting step, some strings present at some nodes are rewritten according to the rewriting rule set and the rewriting mode of the corresponding nodes (by the metarules in the case of changing the rewriting rules). By a communication step, some strings (or copies of some strings) which are present at some node and satisfy some criteria (a trigger) are communicated to one or more other nodes. The language processors at the nodes of the network can work either in synchronous or in asynchronous way.

The triggers, the conditions for communication, can be defined in various manners. The most frequently discussed variants are those ones where filter languages are associated with the nodes for controlling the input/output string flow. A string can be communicated from one node to another one if it is an element of the output filter language of the sender node and it is in the input filter language of the target node.

Variants of communication open a wide variety of classifications of networks of language processors. If each rewriting step is followed by a communication step, then we speak of networks of language processors with nodes communicating by command. If the rewriting continues until a previously prescribed state is reached (a state with a request for communication) and the communication step takes place afterwards, then we speak of NLP systems with components communicating by request.

Workshop 4 Stuttgart, January 1998

Seite 4: vorherige Seite | nächste Seite | Übersicht

NLP systems are both computational and language identifying devices. Languages can be associated to networks of language processors in several manners. For example, we can distinguish a master node and take, as the determined language, all strings which appear at this node during all computations.

State sequences of networks of language processors are of particular interest: is there any periodicity in the behaviour of the system, are there deadlock situations, what can we say about the reachability of the states, about the safety of the system?

In this talk we provide the framework and discuss some variants of NLP systems, including networks of Watson-Crick reactive systems ([7]), a model motivated by DNA computing, and WAVE rewriting systems ([2]), grammatical models of the WAVE paradigm ([14],[15]).

References

[1] E. Csuhaj-Varj?u, Networks of language processors. (A survey). In: Lenguajes Naturales Y Lenguajes Formales XII, (C. Martin-Vide, ed.), PPU, Barcelona, 1996, 169-189. [2] E. Csuhaj-Varj?u and H. Fernau, Grammatical models of the WAVE paradigm. Manuscript, 1997. [3] E. Csuhaj-Varj?u, L. Kari and Gh. P>=aun, Test Tube Distributed Systems Based on Splicing. Computers and Artif. Intelligence 15(2-3) (1996), 211-232.
[4] E. Csuhaj-Varj?u, J. Kelemen and Gh. P>=aun, Grammar Systems with WAVE-like Communication. Computers and Artif. Intelligence 15(5) (1996), 419-436.
[5] E. Csuhaj-Varj?u and G. Rozenberg, Actor Rewriting Systems. In preparation. [6] E. Csuhaj-Varj?u and A. Salomaa, Networks of Parallel Language Processors. In: New Trends in Formal Languages. Control, Cooperation and Combinatorics, (Gh. P>=aun, A. Salomaa, eds.), LNCS 1218, Springer Verlag, Berlin-Heidelberg-New York, 1997, 299-318.
[7] E. Csuhaj-Varj?u and A. Salomaa, Networks of Watson-Crick reactive systems. In preparation. [8] L. Errico and C. Jesshope, Towards a new architecture for symbolic processing. In: Proc. Conf. Artificial Intelligence and Information-Control Systems of Robots' 94, (I. Plander, ed.), World Scientific, Singapore, 1994, 31-40.
[9] R. Freund, E. Csuhaj-Varj?u and F. Wachtler, Test Tube Systems with Cutting/Recombination Operations. In: Pacific Symposium on BIOCOMPUTING'97, (R.B. Altman, et.al eds.), World Scientific, Singapore, 1997, 163-174.
[10] R. Freund and F. Freund, Test Tube Systems or How to Bake a DNA Cake. Acta Cybernetica 12 (1996), 445-459.
[11] S. E. Fahlman, G. E. Hinton, T. J. Seijnowski, Massively parallel architectures for AI: NETL, THISTLE and Boltzmann machines. In: Proc. AAAI- Natl. Conf. on AI., William Kaufman, Los Altos, 1983, 109-113.
[12] C. Hewitt, Viewing Control Structures as Patterns of Passing Messages. J. of Artificial Intelligence 8 (1977), 323-364.
[13] W. D. Hillis, The Connection Machine, MIT Press, Cambridge, 1985.
[14] P.S. Sapaty, The WAVE model for advanced knowledge processing. In: CAD Accelerators, (A. P. Ambler, P. Agrawal, W.R. Moore, eds.), Elsevier Science Publ. B. V., Amsterdam, 1990. [15] P.S. Sapaty, The WAVE paradigm. Internal Report 17/92, Dept. of Informatics, University of Karlsruhe, 1992.

Workshop 5 Stuttgart, January 1998

Seite 5: vorherige Seite | nächste Seite | Übersicht

Some Identities Related to Automata,

Determinants, and M?
obius Functions

Volker Diekert

Institut für Informatik

Universität Stuttgart

Breitwiesenstr. 20{22, D-70565 Stuttgart, Germany

based on joint work with Yuji Kobayashi

Faculty of Science of Toho University, Japan

Möbius functions play an important role in combinatorics. For monoids they were introduced by Cartier and Foata leading to a generalization of Mac Mahon's Master Theorem. The spirit of this theorem is an expression of certain series as the formal inverse of some determinant. In the same spirit Choffrut and Goldwurm have shown recently that (an unambiguous lifting of) the Möbius function of a free partially commutative monoid can be expressed as the determinant of the minimal automaton recognizing the set of lexicographic normal forms, if and only if the independence relation has a transitive orientation. Taking a slightly different viewpoint this result is in fact a statement about languages defined by forbidden factors of length exactly two. The aim of the present talk is a generalization to other classes of languages defined by forbidden factors. The main result states:

Let F ? X? be a finite set of forbidden factors, 1 62 F , and let l = maxfjuj j u 2 Fg, l >= 2, the maximal length. Let S = X? n X?FX? and M be an n?n-matrix associated to the minimal finite automaton recognizing the language S. Then we find explicitly a polynomial D(S; l ? 1) of degree at most n(l ? 1) ? maxf1; (l ? 2)g such that we have the following identity in commuting variables:

S ? Det(1 ?M) ?c D(S; l ? 1):

Workshop 6 Stuttgart, January 1998

Seite 6: vorherige Seite | nächste Seite | Übersicht

On Graph-Controlled Grammars with Leftmost

Derivation

Henning Fernau

Wilhelm-Schickard-Institut für Informatik

Universität Tübingen

Sand 13, D-72076 Tübingen, Germany

email: fernau@informatik.uni-tuebingen.de

We try to study leftmost derivations in regulated rewriting in a systematic way by investigating this notion in the framework of graph-controlled grammars. Since many seemingly different ways of regulation can be seen as special cases of graph-controlled grammars [4], we obtain all known and many new results on leftmost derivation in regulated rewriting (compare the Section 1.4 in the monograph [2]). This work can be seen as continuation of previous works on leftmost derivation, see [1, 5].

Moreover, we want to prove the versatility of graph-controlled grammars as unifying framework for presenting results in regulated rewriting. Taking this approach, some published proofs can be simplified considerably. Moreover, it is useful to detect unexplored sub-areas (which are sometimes surprising findings in view of the maturity of the whole field). For example, there seems to be no previous study of leftmost derivation in time-variant grammars.

Although graph-controlled grammars are not as general as for example selective substitution grammars, see Section 10 in [2], they may provide new insights and view on regulated grammars, so that we promote their use as basic mechanism in regulated rewriting. There is another, pedagogical reason for this promotion: graph-controlled grammars are very intuitive and easy to explain. So, any student or working professional who likes to learn something about regulated rewriting has the chance to get the basics including many of its ramifications quickly. Such things are quite important in our eyes for a rather matured field like regulated rewriting. The need for such systematic presentation is exemplified by the papers [6] and [3], where ideas from regulated rewriting are applied to parsing theory and database theory, respectively, although the papers indicate that the knowledge of basic facts in regulated rewriting is not too widespread.

References

[1] J. Dassow, H. Fernau, and Gh. P>=aun. On the leftmost derivation in matrix grammars. Work in progress, 1997.

[2] J. Dassow and Gh. P>=aun. Regulated Rewriting in Formal Language Theory. Springer, 1989.

[3] G. Dong. Grammar tools and characterizations. In Proceedings of the 11th ACM Symposium on Principles of Database Systems (PODS'92), pages 81{90, 1992.

[4] H. Fernau. Unconditional transfer in regulated rewriting. Acta Inform., 34:837{857, 1997.

[5] H. Fernau and F. Stephan. How powerful is unconditional transfer? |When UT meets AC.|. Technical Report WSI{97{7, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, 1997. Short version to be published in the proceedings of DLT'97.

[6] A. Rußmann. Dynamic LL(k) parsing. Acta Inform., 34:267{289, 1997.

Workshop 7 Stuttgart, January 1998

Seite 7: vorherige Seite | nächste Seite | Übersicht

Structured Formal Verification of a Fragment of

the IBM/390 Clock Chip

Alfons Geser

Symbolisches Rechnen

Wilhelm-Schickard-Institut für Informatik

Sand 13, D-72076 Tübingen

We present a simple and powerful method for formal verification of hardware. First the hardware netlist is translated into a system of term graph rewriting rules that model the state transition behaviour symbolically. This term graph rewriting system is then used to rewrite a specification into normal form, which we can show is a term graph formed exclusively by propositional variables and connectives. In the third phase the propositional term graph is evaluated as a functional decision diagram. From it, one can read off whether verification was successful and if not, efficiently derive a counterexample.

The choice of term graph rewriting, rather than term rewriting, is motivated by the adequate translation that is possible in linear time. Term graph rewriting, as opposed to modal calculi, offers neither quantifiers nor fixed points nor modal operators. However, its expressive power is sufficient to prove bisimulation or reachability of states.

Using a prototype implementation we have successfully verified a fragment of an IBM chip which contains a few symmetries and is complex enough to withstand a naive verification attempt.

Workshop 8 Stuttgart, January 1998

Seite 8: vorherige Seite | nächste Seite | Übersicht