Degrees of ambiguity for parity tree automata

Alexander Rabinovich, Doron Tiferet

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. An automaton is boundedly ambiguous if there is k ∈ N, such that for every input it has at most k accepting computations. We consider Parity Tree Automata (PTA) and prove that the problem whether a PTA is not unambiguous (respectively, is not boundedly ambiguous, not finitely ambiguous) is co-NP complete, and the problem whether a PTA is not countably ambiguous is co-NP hard.

שפה מקוריתאנגלית
כותר פרסום המארח29th EACSL Annual Conference on Computer Science Logic, CSL 2021
עורכיםChristel Baier, Jean Goubault-Larrecq
מסת"ב (אלקטרוני)9783959771757
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2021
אירוע29th EACSL Annual Conference on Computer Science Logic, CSL 2021 - Virtual, Ljubljana, סלובניה
משך הזמן: 25 ינו׳ 202128 ינו׳ 2021

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

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

כנס

כנס29th EACSL Annual Conference on Computer Science Logic, CSL 2021
מדינה/אזורסלובניה
עירVirtual, Ljubljana
תקופה25/01/2128/01/21

ASJC Scopus subject areas

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

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Degrees of ambiguity for parity tree automata'. יחד הם יוצרים טביעת אצבע ייחודית.

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