My Second Day @ ICALP 2008 (Guest Post by MohammadReza Mousavi)

This is the second guest post by MohammadReza Mousavi on ICALP 2008. Thanks to Mohammad for contributing this post! Further information on ICALP may be found at /dev/collective. See here for photos from the conference.

Track B of ICALP started today (7 July) afternoon. My body is not yet totally accustomed to the 24-hours-light scheme here in Reykjavik and thus, I decided take a leave from the morning sessions of Tracks A and C. What you read is a summary of a few talks given at Track B this afternoon. Some of the talks went beyond my limited understanding of their subject matters and thus, you may find inaccuracies in my report of the results, for which I apologize in advance.

Wim Martens: NFA Minimization

There exist well-known efficient state-minimization algorithms for DFA's. It is also known that bisimulation reduction for NFA's is efficient but it does not give you the minimal-state NFA. If I got it well, the bottom line, partially established by the ICALP'08 paper, is that all "interesting" state-minimization problems to non-DFA's (e.g., DFA's with multiple starting states or multiple, no matter how few, transitions with the same label) are NP-hard. By interesting Wim means, if I understood well, those minimizations that can lead to exponential reduction in size.


Hermann Gruber: RE Size

The minimal size of the regular expression for an automaton is known to be exponentially larger than the number of states, given that the alphabet is sufficiently large (due to Ehrenfeucht and Zeiger, JCSS, 1976; preprint available from here). In the present paper, the same result is extended to the case where the alphabet contains at least two elements.

Magnus Johansson: Extended Pi

Magnus presented an interesting extension of Pi in which names are replaced by arbitrary terms which can be equated using arbitrary equational theories (satisfying certain natural properties such as equivariance and equivalence) and also, aliasing for arbitrary terms is allowed (aliasing, or active substitution, basically introduces a new equation). The notion of bisimulation that comes with this this calculus (calculi, parameterized by the equational theory), is a very natural one: it requires the aliases of the two processes to be the same (up to the present equational theory) and the two processes to show the same behavior even under equational theories extended with new equations.