Return to search

Complementation of Büchi automata: A survey and implementation / Komplement till Büchi-automater: En översikt och implementation

<p>This thesis is a survey of the field of languages over infinite sequences. There is active research going on in this field, during the last year several new results where published. </p><p>We investigate the language containment problem for infinite sequences, with focus on complementation of Büchi automata. Our main focus is on the approach with alternating automata by Kupferman&Vardi. The language containment problem has been proved to be in EXPSPACE. We identify some cases when we can avoid the exponential blow-up by taking advantage of properties of the input automaton. </p><p>Some of the algorithms we explain are also implemented in a Sicstus Prolog library.</p>

Identiferoai:union.ndltd.org:UPSALLA/oai:DiVA.org:liu-2192
Date January 2004
CreatorsLindahl, Anders, Svensson, Mattias
PublisherLinköping University, Department of Computer and Information Science, Linköping University, Department of Computer and Information Science, Institutionen för datavetenskap
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, text

Page generated in 0.0019 seconds