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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ינו׳ 2020
אירוע28th EACSL Annual Conference on Computer Science Logic, CSL 2020 - Barcelona, ספרד
משך הזמן: 13 ינו׳ 202016 ינו׳ 2020

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך152

כנס

כנס28th EACSL Annual Conference on Computer Science Logic, CSL 2020
מדינה/אזורספרד
עירBarcelona
תקופה13/01/2016/01/20

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Strongly unambiguous Büchi automata are polynomially predictable with membership queries'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי