Zegel Leiden University
Theoretical Computer Science		 Toren Academiegebouw
Theoretische Informatica Club
* index
* Leiden University
* Department of Computer Science
* Theoretical Computer Science

Schema Voorjaar 1999

woensdag, 16:00 uur, zaal 401

10 February 1999 G. Rozenberg DNA computing in vivo: the arrangement of DNA in ciliates
3 March 1999 Nikè van Vugt Forbidding - enforcing systems
17 March 1999 Pierluigi Frisco Arithmetics with splicing
14 April 1999 Jetty Kleijn Processes of inhibitor nets
28 April 1999 Joost Engelfriet Tree-walking pebble automata and first-order logic
12 May 1999 Rudy van Vliet DNA notation: the case of no nicks
19 May 1999 Jetty Kleijn Processes of inhibitor nets, part 2
26 May 1999 Sebastian Maneth MSO definability of macro tree transductions is decidable

Pierluigi Frisco: Arithmetics with splicing

In the context of splicing we look at the solution of arithmetical problems. In particular a solution to multiplication, division and raising of quantity to any power between integer numbers is given.

Motivations concerning the H system chosen to implement these algorithms are given and, moreover, possible direct translations into other H systems are explained.

Joost Engelfriet: Tree-walking pebble automata and first-order logic

The class TWA of tree languages accepted by (finite state) tree-walking automata is a subclass of the regular tree languages, not known to be proper. Since the regular tree languages are exactly the tree languages definable in monadic second-order logic, it makes sense to compare TWA with the class FO of tree languages definable in first-order logic. Probably, TWA and FO are incomparable. We allow the tree-walking automaton to use a finite number of pebbles, which have to be dropped and lifted in a nested fashion. The corresponding class P-TWA of tree languages is still included in the class of regular tree languages. Moreover P-TWA = FO(TC_1), the class of tree languages definable in first-order logic extended with (monadic) transitive closure.

Rudy van Vliet: DNA notation: the case of no nicks

The structure of DNA-molecules is usually depicted by two-dimensional pictures that (implicitly or explicitly) show the occurring bases and the connections between them. In principle, however, it is also possible to denote the molecules by (one-dimensional) expressions in a formal language, even if these molecules are by far not perfectly complementary double strands.

In this talk, I describe a formal language for DNA-molecules which may contain gaps, caused by the absence of nucleotides in either of the strands. For molecules without nicks, I also present a normal form. Using a characterization of this normal form, which is easy to check, I derive an algorithm to rewrite arbitrary expressions for molecules without nicks into the normal form.

Sebastian Maneth: MSO definability of macro tree transductions is decidable

Graph transductions, i.e., translations from one set of graphs into another, can be defined by formulas in monadic second order logic (MSO). If the input and output graphs are trees, then we obtain a tree-to-tree translation. These translations have been characterized in terms of macro tree transducers.

Now we want to consider the problem to decide, given an arbitrary MTT M, whether the translation realized by M can be defined in MSO. This is proved by first putting M into the ``proper normal form'' which guarantees that every state and parameter of the MTT M generates infinitely many output trees and that M does not delete (the parameters). Now to decide whether the translation realized by an MTT is MSO definable, we put the MTT into proper normal form, and then decide whether the resulting transducer is finite copying. To decide whether an MTT is finite copying is rather straightforward by using the fact that finiteness of ranges of MTTs is decidable.

1999 (MtB)