رسالة جامعية
Complementation of Büchi automata: A survey and implementation ; Komplement till Büchi-automater: En översikt och implementation
| العنوان: | Complementation of Büchi automata: A survey and implementation ; Komplement till Büchi-automater: En översikt och implementation |
|---|---|
| المؤلفون: | Lindahl, Anders, Svensson, Mattias |
| بيانات النشر: | Linköpings universitet, Institutionen för datavetenskap Institutionen för datavetenskap |
| سنة النشر: | 2004 |
| المجموعة: | Linköping University Electronic Press (LiU E-Press) |
| مصطلحات موضوعية: | Datalogi, Infinite sequences, Alternating automata, Complementation, Omega-regular, Büchi automata, Computer Sciences, Datavetenskap (datalogi) |
| الوصف: | 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. 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. Some of the algorithms we explain are also implemented in a Sicstus Prolog library. |
| نوع الوثيقة: | bachelor thesis |
| وصف الملف: | application/pdf |
| اللغة: | English |
| العلاقة: | http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-2192Test |
| الإتاحة: | http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-2192Test |
| حقوق: | info:eu-repo/semantics/openAccess |
| رقم الانضمام: | edsbas.6889BBC4 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |