<=<= <=<= <=<= <=<= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= <= 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   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  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  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  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  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  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  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  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  Minimality and Decidability Results Concerning Generating Systems of Primitive Recursive Functions S?andor Horv?ath Department of Computer Science Eötvös Lor?and University M?uzeum kör?ut 6-8., II. 2-3, Budapest H-1088, Hungary email: horvath@cs.elte.hu Joint work with Holger Petersen We consider the class of primitive recursive functions (the definition can be found in textbooks on computability, e.g. [3, 7, 8, 9]). As this class includes most of the functions usually encountered in elementary arithmetic it is of some interest to find simple characterizations for it. Significant simplifications in the recursion scheme employed in the definition of the primitive recursive functions have been found by Gladstone [4, 5]. Further research in this direction is reported in [2]. We are interested in the initial functions underlying the class of primitive recursive functions. We reduce the set of initial functions to a minimum that cannot be simplified further without losing some functions. We also deal with the class of partial recursive functions and eliminate some initial functions from a known generating system for this class. Finally, we consider some decidability questions concerning program length and recursiondepth. Lemma 1 If from a set of initial functions all primitive recursive functions can be obtained by composition and primitive recursion then it necessarily contains an n- or (n + 1)-place function for every n >= 1. Theorem 1 Every primitive recursive function can be obtained by a finite number of applications of composition and primitive recursion from the following functions: 1. The successor function S. 2. The projections U31 and U2n+5 2 , n >= 0. Moreover this set of initial functions is minimal in the sense that not all primitive recursive functions can be obtained from a proper subset of these functions. If the 0-place functions (constants) are also considered as primitive recursive we get the following statement: Theorem 2 Every primitive recursive function including constants can be obtained by a finite number of applications of composition and primitive recursion from the initial functions given in the preceding theorem and any 0-place function. This set of initial functions is minimal. Workshop 9 Stuttgart, January 1998  It is possible to show results analogous to the preceding theorem if the role of the projection U31 is interchanged with U2m+1 1 for some m >= 2 (U31 is replaced by U32 and U2m+1 2 is replaced by U2m+1 1 ). If ? is added to the operations in Theorem 1 all partial recursive functions can be derived. However Lemma 1 does not remain valid. We have: Theorem 3 Every partial recursive function can be obtained by a finite number of applications of composition, primitive recursion, and unbounded minimization from the initial functions S, U31, and any infinite subset of fUk2 j k >= 2g. In [6] a generating system for the set of partial recursive functions is given equipped with the initial functions N , U11, and S. Its operations are composition, primitive recursion, minimization, and attachments of new variables to the left or to the right. The function N can be omitted by applying ? to U21. From Theorem 1 we get another reduction of the set of initial functions: Theorem 4 Every partial recursive function can be obtained from the initial functions S and N by composition, primitive recursion, minimization, and attachments of new variables. By a standard numerical encoding of the representations of the one-place partial recursive functions (in Kleene's classical generating system), regarding the code numbers as \abstract programs", and assigning to every abstract program, as its \length", the length of the original representation (of the corresponding partial recursive function), we clearly get an (axiomatic) Blum program size measure. Within the above encoding, the (abstract) programs of the one-place primitive recursive functions form a subrecursive enumeration, see [1]. So by a general result we have that the set SP (primrec) of the shortest programs of the one-place primitive recursive functions is recursively enumerable. On the other hand it is also known that the analogous set SP (partrec) (of the shortest programs of all the one-place partial recursive functions) is immune (i.e., infinite, and contains no infinite r.e. subset). Now we formulate the following Problem 1 Is SP (primrec) not recursive? Meyer and Ritchie's loop programs compute exactly the primitive recursive functions. It is known (see [1]) that the \complexity problem" of loop programs is undecidable for loop-depth >= 3. (This means that if an arbitrary loop program ß has loop-depth n >= 3 then it is undecidable whether there exists an equivalent loop program ß0 with loop-depth n ? 1.) According to loopdepth we obtain Meyer and Ritchie's well-known hierarchy fLngn>=0 (within the class of primitive recursive functions). A related hierarchy is Axt's hierarchy fKngn>=0, in which the role of loopdepth is played by the depth of primitive recursion. If we allow the more general simultaneous primitive recursion, too, we get a modification fKsim n gn>=0 of Axt's hierarchy. It is known that the hierarchies fLngn>=0 and fKsim n gn>=0 coincide, and Ln = Kn for n >= 4. Clearly we can construct an effective translation of the loop programs into the representations of the primitive recursive functions in which simultaneous primitive recursion is allowed, too, such that, under this translation, loop-depth n is always mapped into recursion-depth n, for every n >= 0. We can get an analogous effective translation of the loop programs into the \simple" representations of the primitive recursive functions (in which simultaneous primitive recursion is not allowed), for loop-depth n >= 4. So, in view of the above we have: Proposition 1 The problem of reducibility of recursion-depth n in the hierarchy fKsim n gn>=0 is undecidable for n >= 3, and the analogous problem in the Axt hierarchy is undecidable for n >= 5. Problem 2 Is the reducibility of recursion-depth n in the Axt hierarchy undecidable for n = 3; 4, too? References [1] Giorgio Ausiello. Complessit?a di calcolo delle funzioni. Editore Boringhieri, Torino, 1975. Workshop 10 Stuttgart, January 1998  [2] Christian Calude and Lila S^antean. On a theorem of Günter Asser. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 36:143{147, 1990. [3] Martin Davis. Computability & Unsolvability. McGraw-Hill Series in Information Processing and Computers. McGraw-Hill Book Company, New York, Toronto, London, 1958. [4] M. D. Gladstone. A reduction of the recursion scheme. Journal of Symbolic Logic, 32:505{ 508, 1967. [5] M. D. Gladstone. Simplifications of the recursion scheme. Journal of Symbolic Logic, 36:653{665, 1971. [6] S?andor Horv?ath. Finite, simple generating systems for partial recursive functions|a short note. Bulletin of the European Association for Theoretical Computer Science (EATCS), 28:30{32, 1986. [7] Michael Machtey and Paul Young. An Introduction to the General Theory of Algorithms. Theory of Computation Series. North Holland, New York, 1978. [8] Claus-Peter Schnorr. Rekursive Funktionen und ihre Komplexität. B. G. Teubner, Stuttgart, 1974. [9] George J. Tourlakis. Computability. Reston Publ. Co., Inc., A Prentice-Hall Company, Reston, Virginia, 1984. Workshop 11 Stuttgart, January 1998  Once More on the Context-Freeness of Q \ (ab?)n L?aszl?o K?aszonyi Department of Mathematics Berzsenyi College H-9700 Szombathely Let Q be the language consisting of primitive words over the alphabet fa; bg and consider the language Ln = Q \ (ab?)n. It is conjectured that Ln is context-free for all n 2 N . The validity of the conjecture is proved for n-s having special number-theoretic character. The proofs of these results are based on the well-known theorem of Ginsburg, which asserts | applied to our case | that Ln is context-free iff the set E(Ln) = f(e0; : : : ; en?1) 2 Nn j abe0 ? ? ? aben?1 2 Lng is a stratified semilinear set. Here we give a decomposition of E(Ln) in special components and conjecture that each of these components is a stratified semilinear set. We prove the validity of the conjecture in a special case. (Joint work with M. Katsura) Workshop 12 Stuttgart, January 1998  On General Iteration Lemmata Manfred Kudlek Fachbereich Informatik, Universität Hamburg Vogt-Kölln-Straße 30, 22527 Hamburg email: kudlek@informatik.uni-hamburg.de 1 Introduction The iteration lemmata for regular, linear and context-free languages are well known. They are based on the catenation operation ( with unit element >= ) on the free monoid V ? over some alphabet V , and the norm jwj ( length of words ). In this paper other binary operations ffi on the power set on underlying monoids M are introduced, as well as other general norms ?. The operations have to be associative with zero element ; and unit element f>=g, and distributive with [ such that the resulting structure is an !-complete semiring. The norm ? has to be monotone with respect to ffi and [, with some minimal norms for ; and f>=g, and be defined for all finite sets. If rational, linear and algebraic languages are defined as fixed points of corresponding systems of equations on !-complete semirings, it can be shown that iteration lemmata similar to the classical ones hold for such languages. 2 Definitions Let M be a monoid with binary operation ffi and unit element >=. Extend ffi to an associative binary operation ffi : P(M) ? P(M)!P(M ), distributive with [ ( A ffi (B [ C) = (A ffi B) [ (A ffi C) and (A [ B) ffi C = (A ffi B) [ (B ffi C) ), with unit element f>=g ( f>=g ffi A = A ffi f>=g = A ), and zero element ; ( ; ffi A = A ffi ; = ; ). Then S = (P(M); [; ffi; ;; f>=g) is an !-complete semiring, i.e. if Ai ? Ai+1 for 0 <= i then B ffi S i>=0 Ai = S i>=0(B ffi Ai) and (S i>=0 Ai) ffi B = S i>=0(Ai ffi B). Define also Affi(0) = f>=g; Affi(1) = A; Affi(k+1) = A ffi Affi(k); Affi = S k>=0 Affi(k): Let ? : P(M)!IN be a ( partial ) function ( norm ) defined for all finite sets, with the following properties : ?(;) <= 1 ; ?(f>=g) <= 1 ; A ? B)?(A) <= ?(B) ; ?(A); ?(B) <= ?(A [ B) <= maxf?(A); ?(B)g; ?(A); ?(B) <= ?(A ffi B) <= ?(A) + ?(B) ; (A 6= ; ^ A 6= f>=g))?(Affi) = 1 : Example 1 : Let ffi = ?, the usual catenation ( being associative with unit element >= on M = V ? ), and ? be defined by ?(;) = ?(f>=g) = 0 ; w 2 V ?)?(fwg) = jwj ; ?(A ffi B) = ?(A) + ?(B) ; ?(A [ B) = maxf?(A); ?(B)g ; ?(Affi) = 1 : Example 2 : Let ffi = , the shuffle operation ( being associative and commutative on M = V ? with unit element >= ), and ? be defined as in Example 1. Example 3 : Let V be an alphabet and I ? V ? V a symmetric, not necessarily reflexive, relation, called an independence relation. Define uabv ? ubav if (a; b) 2 I and consider its reflexive and transitive closure ??. Then ?? is an equivalence relation, and the set M = V ?= ??, also written V ?=I , being a monoid, is called the trace monoid of V with respect to I . For t1 = [u]; t2 = [v] 2 M the binary operation on traces is defined by t1 ffi t2 = [uv], and the neutral element is [>=]. For t = [w] 2 M a norm can be defined by ?(t) = jwj. Workshop 13 Stuttgart, January 1998  Let X = fX1; : : : ; Xng be a set of variables such that X \ M = ;. A monomial over S with variables in X is a finite string of the form : A1 ffiA2 ffi : : : ffiAk ; where Ai 2 X or Ai ? M; jAij < 1; i = 1; : : : ; k: ( without loss of generality, Ai = fffig with ffi 2 M suffices ). A polynomial p(X) over S is a finite union of monomials where X = (X1; ? ? ? ; Xn). A system of equations over S is a finite set of equations : E = fXi = pi(X) j i = 1; : : : ; ng; where pi(X) are polynomials. The solution of E is a n-tuple (L1; : : : ; Ln) of languages over M , with Li = pi(L1; : : : ; Ln) and the n-tuple is minimal with this property, i.e. if (L01; : : : ; L0n) is another n-tuple that satisfies E, then (L1; : : : ; Ln) <= (L01; : : : ; L0n) ( where the order is defined componentwise with respect to inclusion ). From the theory of semirings follows that any system of equations over S has a unique solution, and this is the least fixed point starting with (X1; ? ? ? ; Xn) = (;; ? ? ? ; ;). A system of equations is called linear if all monomials are of the form A ffi X ffi B or A, and rational if they are of the form X ffi A or A, with A ? M and B ? M . Corresponding families of languages ( solutions of such systems of equations ) are denoted by ALG(ffi), LIN(ffi), and RAT (ffi). If ffi is commutative then ALG(ffi) = LIN(ffi) = RAT (ffi). 3 Results The following theorems can be proven in a way analogous to the classical iteration lemmata. Theorem 1 : Let L 2 RAT (ffi) with L ? M . Then there exist n(L) > 0 such that, for any w 2 L with ?(fwg) >= n(L), there exist x1; x2; x3 2 M such that : (i) w 2 fx1g ffi fx2g ffi fx3g. (ii) 0 < ?(fx1g ffi fx2g) <= n(L). (iii) fx1g ffi fx2gffi ffi fx3g ? L. Theorem 2 : Let L 2 LIN(ffi) with L ? M . Then there exist n(L) > 0 such that, for any w 2 L with ?(fwg) >= n(L), there exist x1; x2; x3; x4; x5 2 M such that : (i) w 2 fx1g ffi fx2g ffi fx3g ffi fx4g ffi fx5g. (ii) ?(fx1g ffi fx2g ffi fx4g ffi fx5g) <= n(L). (iii) 0 < ?(fx2g ffi fx4g) (iv) 8k >= 0 : fx1g ffi fx2gffi(k) ffi fx3g ffi fx4gffi(k) ffi fx5g ? L. Theorem 3 : Let L 2 ALG(ffi) with L ? M . Then there exist n(L) > 0 such that, for any w 2 L with ?(fwg) >= n(L), there exist x1; x2; x3; x4; x5 2 M such that : (i) w 2 fx1g ffi fx2g ffi fx3g ffi fx4g ffi fx5g. (ii) ?(fx2g ffi fx3g ffi fx4g) <= n(L). (iii) 0 < ?(fx2g ffi fx4g) (iv) 8k >= 0 : fx1g ffi fx2gffi(k) ffi fx3g ffi fx4gffi(k) ffi fx5g ? L. To prove these theorems the systems of equations are first converted into equivalent systems of equations ( with additional variables ) where all monomials are in normal form ( X ffi Y or ff for algebraic, ff ffi X or X ffi ff or ff for linear, and X ffi ff or ff for rational systems ). Any w 2 L can be generated as w 2 ffi1g ffi ? ? ? ffi ffikg where the fij 2 M are the leaves of a binary derivation tree with respect to ffi, and the children of each node correspond to monomials. Note that ? is monotone with respect to [ and ffi, but bounded by the sum. References 1 J. S. Golan : The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science. Longman Scientific and Technical, 1992. 2 W. Kuich, A. Salomaa : Semirings, Automata, Languages. EATCS Monographs on Theoretical Computer Science, Springer, Berlin, 1986. Workshop 14 Stuttgart, January 1998  Dense Completeness Klaus-Jörn Lange Theoretische Informatik / Formale Sprachen Wilhelm-Schickard-Institut für Informatik Sand 13, D-72076 Tübingen Formal Language Theory and Structural Complexity Theory exhibit close relationships. In spite of the fact that both theories pursue comparable questions like, e.g., the comparison of determinism and nondeterminism, they both succeed quite differently in answering these questions. While Complexity Theory is to a large extent a collection of open problems and most of its results relate open problems, the phenomenon of open problems is almost unknown in Formal Language Theory. This raises the question, how close their mutual relationship is. Almost all formal languages that are in some way context-free, are related to the classes NP, NAuxPDApt, NSPACE(log n), or NC1. Analogous relations hold between deterministic versions of these families and the classes P, DAuxPDApt, DSPACE(logn), and NC1. The type of these relations is that a family of formal languages A is contained in a complexity class B and that A contains a B-complete language. Based on an observation by Richard Beigel it is now possible to construct in a systematic way for a class of formal languages A, defined by sequential one-way automata and for which the class B is closed under logspace reductions, a type of nondeterministic one-way automata, such that for a corresponding class of languages A0 it holds that A ? A0 ? B and 8B2B9A2A0 : LOG(A) = LOG(B): The family A0 thus lies dense in the class B. The construction and some of its properties will be presented in the lecture. It is open whether a comparable construction can be found for deterministic families or classes below DSPACE(logn). Workshop 15 Stuttgart, January 1998  Confluence of Terminating 2{Dimensional String Rewriting Systems is Undecidable Markus Lohrey Institut für Informatik Universität Stuttgart Breitwiesenstr. 20{22, D-70565 Stuttgart 2{dimensional string rewriting systems are a straight forward generalization of ordinary string rewriting systems. Given two finite alphabets ?1 and ?2, a 2{dimensional string rewriting system over (?1; ?2) is a finite set R of rules of the form (l1; l2) ! (r1; r2), where l1; r1 2 ?1 and l2; r2 2 ?2. As expected, R defines a 1{step rewrite relation !R by (u1; u2) !R (v1; v2) iff there exist a rule (l1; l2) ! (r1; r2) in R and strings u01; u002 2 ?1, u02; u002 2 ?2 such that u1 = u01l1u001, u2 = u02l2u002 and v1 = u01r1u001, v2 = u02r2u002. Thus, 2{dimensional string rewriting is a special case of trace rewriting. For ordinary string rewriting systems it is known to be decidable whether a given terminating string rewriting system is confluent. In contrast to this result, I will prove that the question whether a terminating 2{dimensional string rewriting system over (f1g; ?) is confluent is undecidable. The proof is based on a technique developed by Narendran and Otto. Workshop 16 Stuttgart, January 1998  The Code Problem for Trace Monoids Anca Muscholl Institut für Informatik Universität Stuttgart Breitwiesenstr. 20{22, D-70565 Stuttgart The topic of codes in the framework of trace monoids leads to interesting and challenging decision problems of combinatorial flavour. We consider in this talk the unique decipherability problem (code problem), i.e. the question whether a (finite) subset X of a trace monoid generates a free monoid. The code problem is in general undecidable, yet there is no exact characterization of the trace monoids where this problem is decidable. We establish in this talk the decidability resp. undecidability of the code problem for some particular families of graphs (i.e., commutation relations I). These results are tightly connected to the emptiness problem for certain types of multicounter automata. Workshop 17 Stuttgart, January 1998  On Some Recognizable Picture-Languages ? Klaus Reinhardt Wilhelm-Schickard-Institut für Informatik Universität Tübingen Sand 13, D-72076 Tübingen, Germany email: reinhard@informatik.uni-tuebingen.de In [GRST94] pictures are defined as two-dimensional rectangular arrays of symbols of a given alphabet. A set (language) of pictures is called recognizable if it is recognized by a finite tiling system. It was shown in [GRST94] that a picture language is recognizable iff it is definable in existential monadic second-order logic. In [Wil97] it was shown that star-free picture expressions are strictly weaker than first-order logic. A comparison to other regular and contextfree formalisms to describe picture languages can be found in [Mat97b, Mat97a]. We show that the language of pictures over fa; bg, where all occurring b's are connected is recognizable, which solves an open problem in [Mat97a]. (Connectedness is not recognizable in general [FSV95].) Furthermore we show that the language of pictures over fa; bg, where the number of a's is equal to the number of b's is nonuniformly recognizable. Hereby we use counters similar to those used in [Für82]. References FSV95 Ronald Fagin, Larry J. Stockmeyer, and Moshe Y. Vardi. On monadic NP vs. monadic co-NP. Information and Computation, 120(1):78{92, July 1995. Für82 Martin Fürer. The tight deterministic time hierarchy. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 8{16, San Francisco, California, 5{7 May 1982. GRST94 Dora Giammarresi, Antonio Restivo, Sebastian Seibert, and Wolfgang Thomas. Monadic second-order logic over pictures and recognizability by tiling systems. Proceedings of the 11th STACS 94, LNCS 775, pages 365{375, 1994. Mat97a Oliver Matz. On Piecewise Testable, Starfree, amd Recignizable Picture Languages, 1997. Mat97b Oliver Matz. Regular expressions and context-free grammars for picture languages. In 14th Annual Symposium on Theoretical Aspects of Computer Science, volume 1200 of lncs, pages 283{294, Lübeck, Germany, 27 February{ March 1 1997. Springer. Wil97 Thomas Wilke. Star-free picture expressions are strictly weaker than first-order logic. In Automata, Languages and Programming, LNCS 1256 , pages 347{357, 1997. ?This research has been supported by the DFG Project La 618/3-1 KOMET. Workshop 18 Stuttgart, January 1998  On the Power of Parallel Communicating Grammar Systems György Vaszil Computer and Automation Research Institute Hungarian Academy of Sciences Kende u. 13-17, H-1111 Budapest, Hungary Parallel communicating grammar systems, introduced in [5], are formal language theoretic models of parallel and distributed computation. In these systems several grammars are working on their own sentential forms in parallel and their work is organized in a communicating system to generate a single language. PC grammar systems have been the subject of detailed study over the past few years, see [1],[4]. Here we report on new results from [3],[2] and [6], concerning the generative power of PC grammar systems with context-free rules. We show that these systems generate all recursively enumerable languages, by demonstrating how they can simulate two-counter machines, a restricted but computationally complete class of Turing machines. References 1 E. Csuhaj-Varj?u, J. Dassow, J. Kelemen, Gh. P<=aun, Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994. 2 E. Csuhaj-Varj?u, Gy. Vaszil, On synchronization in context-free PC grammar systems, submitted, 1997. 3 E. Csuhaj-Varj?u, Gy. Vaszil, Context-free PC grammar systems are computationally complete, submitted, 1997. 4 J. Dassow, Gh. P<=aun, G. Rozenberg, Grammar Systems. Chapter 4. Handbook of Formal Languages, ed. by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin, 1997, 155-213. 5 Gh. P<=aun, L. Santean, Parallel communicating grammar systems: the regular case, Ann. Univ. Bucharest, Ser. Matem.-Inform. 38, 2 (1989), 55-63. 6 Gy. Vaszil, On parallel communicating Lindenmayer systems, In: Grammatical Models of Multi- Agent Systems (Gh. P<=aun, A. Salomaa, eds.), Gordon and Breach Science Publishers, to appear. Workshop 19 Stuttgart, January 1998