Deciding semantic finiteness of first-order grammars w.r.t. bisimulation equivalence
- 11:00 25th January 2017 ( week 2, Hilary Term 2017 )Room 441, Wolfson Building
The plan is to explain the main ideas of the MFCS'16 paper
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6464,
by figures (and without formalities).
The presented decidability proof for semantic finiteness (or "regularity") of first-order grammars (that encompass pushdown automata) w.r.t. bisimulation equivalence relies on the decidability of bisimulation equivalence (which was first proven by Senizergues).