Duality in Computer Science

Abstract

In the regular languages, both the topological and algebraic approach have proven to be very fruitful. This thesis extends both approaches to work for non-regular languages, focused on two particular cases: 1) The visibly pushdown languages. Here, finite algebraic recognisers are developed and the topological perspective is built on this foundation. 2) Complexity- and logic classes. This part focuses in particular on the effects of the block product on the topological perspective.