Dear all,

We will have our next LIRa session tomorrow, on Thursday, 16 February 16:30.

This will be a hybrid session. If you want to attend online, please use our recurring zoom link: https://uva-live.zoom.us/j/89230639823?pwd=YWJuSnJmTDhXcWhmd1ZkeG5zb0o5UT09 (Meeting ID: 892 3063 9823, Passcode: 421723)

You can find the details of the talk below.

Speaker: Jos Baeten (CWI)

Date and Time: Thursday, February 16th 2023, 16:30-18:00

Venue: ILLC seminar room F1.15 in Science Park 107 and online.

Title: Pushdown Automata and Context-Free Grammars in Bisimulation Semantics

Abstract. The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reactive Turing Machine, transitions have labels to give a notion of interactivity. In the resulting process graph, we use bisimilarity instead of language equivalence.

Subsequently, we considered other classical theorems and notions from automata theory and formal languages theory. In this talk, we consider the classical theorem of the correspondence between pushdown automata and context-free grammars. By changing the process operator of sequential composition to a sequencing operator with intermediate acceptance, we get a better correspondence in our setting. We find that the missing ingredient to recover the full correspondence is the addition of a notion of state awareness.

Hope to see you there!

The LIRa team