CONCUR 2004 START ConferenceManager    

Message-Passing Automata are expressively equivalent to EMSO Logic

Benedikt Bollig and Martin Leucker

Presented at Fifteenth International Conference on Concurrency Theory (CONCUR 2004), London, England, 31 August - 3 September, 2004


We study the expressiveness of finite message-passing automata with a priori unbounded channels and show them to capture exactly the class of MSC languages that are definable in existential monadic second-order logic interpreted over MSCs. Moreover, we prove the monadic quantifier-alternation hierarchy over MSCs to be infinite and conclude that the class of MSC languages accepted by message-passing automata is not closed under complement. Furthermore, we show that satisfiability for (existential) monadic seconder-order logic over MSCs is undecidable.

START Conference Manager (V2.47.4)