3 results
Benedikt Bollig.
Visibly pushdown automata are input-driven pushdown automata that recognize some non-regular context-free languages while preserving the nice closure and decidability properties of finite automata. Visibly pushdown automata with multiple stacks have been considered recently by La Torre, Madhusudan, […]
Published on December 24, 2008
Benedikt Bollig ; Dietrich Kuske ; Ingmar Meinecke.
We examine a bidirectional propositional dynamic logic (PDL) for finite and infinite message sequence charts (MSCs) extending LTL and TLC-. By this kind of multi-modal logic we can express properties both in the entire future and in the past of an event. Path expressions strengthen the classical […]
Published on September 4, 2010
Benedikt Bollig ; Alain Finkel ; Amrita Suresh.
The undecidability of basic decision problems for general FIFO machines such as reachability and unboundedness is well-known. In this paper, we provide an underapproximation for the general model by considering only runs that are input-bounded (i.e. the sequence of messages sent through a particular […]
Published on January 20, 2022