 |
|
Leiden University
Theoretical Computer Science |
|
|
| Theoretische
Informatica
Club |
| 30.1 |
G. Rozenberg |
Forbidding and enforcing |
| 13.2 |
J. Engelfriet |
Derivation trees of ground term rewriting systems |
| 20.2 |
E. Csuhaj-Varjú |
Networks of language processors |
| 27.2 |
J. Hage |
Embedding in 2-classes of group labeled 2-structures |
| 3.4 |
H. J. Hoogeboom |
Traces, an introduction |
| 17.4 |
Tj. Gelsema |
An introduction to the pi-calculus |
| 15.5 |
M. ter Beek |
Logic grammars and natural language |
| 29.5 |
S. Maneth |
Tree transductions defined by monadic second order logic |
| 5.6 |
N. van Vugt |
DNA Computing: basic models |
| 19.6 |
H.C.M. Kleijn |
Petri Nets and generalizations of traces |
|
|
|
Samenvattingen
Joost Engelfriet:
Derivation trees of ground term rewriting systems
A notion of derivation tree is introduced for ground term rewriting systems,
generalizing the one for context-free grammars. Each derivation tree models the
derivation of one ground term into another, modulo interchanging of independent
derivation steps. The set of derivation trees of a given ground term rewriting
system forms a regular tree language, i.e., can be recognized by a bottom-up
tree automaton (a special type of ground term rewriting system). Using the
theory of regular tree languages (which generalizes, and is part of, formal
language theory) new proofs of known results can be given: (1) viewed as tree
grammars, ground term rewriting systems generate regular tree languages, and
(2) confluence and termination are decidable for ground term rewriting systems.
E. Csuhaj-Varjú:
Networks of language processors
The theory of networks of language processors is an important subfield of
grammar systems theory, a recent vivid area of formal languages. A network of
language processors (an NLP system) consists of several language identifying
devices (language processors) associated with nodes of a network (in particular
case with nodes of a virtual complete graph). The processors rewrite strings
(representing the current state of the nodes) according to some prescribed
rewriting mode and communicate them along the network via input and output
filter languages. NLP systems are both computational and language identifying
devices, providing models and frameworks for parallel and distributed symbolic
processing.
In this talk we give an overview about the most important particular cases of
networks of language processors, motivated by the Wave paradigm of active
knowledge networks and/or DNA computing.
Jurriaan Hage:
Embedding in 2-classes of group labeled 2-structures
A group labeled 2-structure is intuitively a complete graph on some domain
D whose edges are labeled with elements of
some group Gamma. Given a group labeled
2-structure g we define how to generate an
equivalence class of group labeled 2-structures [g]
from g.
After introducing these concepts more formally and in more detail the talk
will concern the following problem for 2-classes: given a non-complete
group labeled 2-structure h' on some domain
D', is it possible to find
h in [g]
such that h' can be embedded in
h?
It turns out that although the size of [g]
is exponential in the number
of nodes, that this does not make the problem infeasible.
We also give some methods of optimization, more specifically a way
to transform the patterns we are looking for in a group labeled
2-structure to smaller ones.
Hendrik Jan Hoogeboom:
Traces, an introduction
The theory of traces, introduced by Mazurkiewicz to describe the
behaviour of concurrent systems, is one of the topics that were extensively
studied here in Leiden. Basically, a trace is an equivalence class of
words, grouping together different sequential observations of the same
concurrent process.
I propose to split the presentation into two parts. First, a zero knowledge
introduction to traces and trace languages.
Then, in the second hour, we can consider asynchronous automata, a
distributed (Petri net-like) automaton model particularly suited to accept
('recognizable') trace languages. Zielinka's proof that every recognizable
trace language is accepted by an asynchronous automaton is not very well
understood. I will try to explain one of the basic concepts behind the
construction.
Note. The first hour may be very boring to people that know trace theory.
Tjalling Gelsema:
An introduction to the pi-calculus
The pi-calculus, an extension of the process algebra CCS, is a process
calculus of communicating systems. One of the main features of the
pi-calculus is mobility, i.e., the ability of processes to change their
communication structure during computation. In this talk, this feature
will be exploited by some examples. We also present the semantics of the
pi-calculus in terms of a labeled transition system, and we show some of
the various types of bisimulation that are based upon this semantics.
Finally, we give some results on structural equivalence and structural
inclusion of pi-calculus processes.
Maurice ter Beek:
Logic grammars and natural language
In this talk an overview of the field of logic grammars is given, based on
[AD]. Firstly, their basic features are introduced and the way in which
they differ fr om Chomsky grammars is explained. It is then shown how they can
be used to describe natural as well as formal languages.
Secondly, three types of logic grammars (Metamorphosis Grammars, Definite
Clause Grammars and Extraposition Grammars) are introduced and they are shown
to easily capt ure enhanced features of natural language. This is concluded by
a comparison of the three types.
Thirdly, some generalizations of the above types of grammars (Discontinuous
Grammars and Static Discontinuity Grammars) are introduced for further
expressive power. Also the way these grammars can describe natural and formal
languages is illustrated. Finally, the subjacency principle of Chomsky's
Government and Binding theory is e xplained and it is indicated how to express
this in Static Discontinuity Grammars.
[AD] Harvey Abramson and Veronica Dahl, Logic Grammars, Springer,
1989.
Sebastian Maneth:
Tree transductions defined by monadic second order logic
Graph transductions, i.e., translations from one set of graphs into another,
can be defined by formulas in monadic second order logic (MSO) in the
following way. If g is a source graph then the nodes of the target graph
h are defined by means of MSO formulas with one free variable to be
interpreted in g. The edges of h are defined by MSO formulas with two
free variables, defining a binary relation on the nodes of g (and then
restricting them to the nodes of h).
If the source and target graphs are trees then MSO transductions describe
tree-to-tree translations, called MSO tree transductions. We compare
this class of transductions with known classes of tree transductions. In
particular we compare it with the macro tree transducer which is a
formal model for syntax-directed semantics in which context information can
be handled. It turns out that macro tree transducers which are restricted
in a certain way correspond to the MSO tree transductions.
Nikè van Vugt:
DNA Computing: basic models
We will discuss three models of DNA computing: Adleman's
method to find a Hamiltonian path in a given graph by
using the tools of molecular biology, Lipton's model to
solve instances of the satisfiability problem, and splicing
systems, which provide a formal description of the generative
power of restriction enzymes acting on DNA molecules.
No prior knowledge is assumed.
Jetty Kleijn:
Petri Nets and generalizations of traces
Petri nets are an example of a successful model of distributed (concurrent)
systems. The trace theory of Mazurkiewicz provides a means to describe the
behaviour of certain basic classes of Petri nets. For more general Petri nets
however, Mazurkiewicz' traces are too restricted. In this talk we discuss
Petri nets, traces, and some generalizations of traces, in particular the
so-called local traces. No prior knowledge in this area is assumed.
6.6.97 (MtB,HJH)
