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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يناير 2021
الحدث29th EACSL Annual Conference on Computer Science Logic, CSL 2021 - Virtual, Ljubljana, سلوفينيا
المدة: ٢٥ يناير ٢٠٢١٢٨ يناير ٢٠٢١

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

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

!!Conference

!!Conference29th EACSL Annual Conference on Computer Science Logic, CSL 2021
الدولة/الإقليمسلوفينيا
المدينةVirtual, Ljubljana
المدة٢٥/٠١/٢١٢٨/٠١/٢١

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “Degrees of ambiguity for parity tree automata'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا