<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>
| Identifer | oai:union.ndltd.org:UPSALLA/oai:DiVA.org:liu-2192 |
| Date | January 2004 |
| Creators | Lindahl, Anders, Svensson, Mattias |
| Publisher | Linköping University, Department of Computer and Information Science, Linköping University, Department of Computer and Information Science, Institutionen för datavetenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, text |
Page generated in 0.0018 seconds