Strongly unambiguous Büchi automata are polynomially predictable with membership queries

Dana Angluin, Timos Antonopoulos, Dana Fisman

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

A Büchi automaton is strongly unambiguous if every word w ∈ Σω has at most one final path. Many properties of strongly unambiguous Büchi automata (SUBAs) are known. They are fully expressive: every regular ω-language can be represented by a SUBA. Equivalence and containment of SUBAs can be decided in polynomial time. SUBAs may be exponentially smaller than deterministic Muller automata and may be exponentially bigger than deterministic Büchi automata. In this work we show that SUBAs can be learned in polynomial time using membership and certain non-proper equivalence queries, which implies that they are polynomially predictable with membership queries. In contrast, under plausible cryptographic assumptions, non-deterministic Büchi automata are not polynomially predictable with membership queries.

اللغة الأصليةإنجليزيّة أمريكيّة
عنوان منشور المضيف28th EACSL Annual Conference on Computer Science Logic, CSL 2020
المحررونMaribel Fernandez, Anca Muscholl
ناشرSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
رقم المعيار الدولي للكتب (الإلكتروني)9783959771320
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يناير 2020
الحدث28th EACSL Annual Conference on Computer Science Logic, CSL 2020 - Barcelona, أسبانيا
المدة: ١٣ يناير ٢٠٢٠١٦ يناير ٢٠٢٠

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت152

!!Conference

!!Conference28th EACSL Annual Conference on Computer Science Logic, CSL 2020
الدولة/الإقليمأسبانيا
المدينةBarcelona
المدة١٣/٠١/٢٠١٦/٠١/٢٠

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “Strongly unambiguous Büchi automata are polynomially predictable with membership queries'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا