Place: BASICS Meeting Room (3-318)

Time: 10am, Friday November 28, 2008

Talk 1:

Undecidable properties on length-two string rewriting systems
Masahiko Sakai (Nagoya University)

Length-two string rewriting systems are string rewriting systems in
which every rule is s -> t for length-two string s and t. This talk
shows that confluence, termination, left-most termination and
right-most termination are undecidable properties for length-two
string rewriting systems. These results mean that these properties
are undecidable for the class of linear term rewriting systems in
which depth-two variables are allowed in both sides of rules.

Talk 2:
SOS formats for process languages
Shoji Yuen (Nagoya University)

Structural Operational Semantics is a simple and flexible way to define
operational semantics for various programming languages. As Milner
defined CCS semantics by SOS, a labelled transition semantics is usually
defined by SOS. The congruence property of process languages is the
main issue for the well definedness of process languages. Since SOS
rules of the language play the main role to show the congruence
property, a meta-theory to get the property has been studied according
to the syntactic nature of SOS rules. We have been investigating the
syntactic patterns, called "formats", with the congruence property for
the weak semantics. And we also studied several properties for timed
process languages. For timed process languages, in addition to the
congruence propertiy, some fundamental properties of time passage are
studied. (Joint work with Irek Ulidowski.)