English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study minimization problems for deterministic $\omega$-automata in thepresence of don't care words. We prove that the number of priorities indeterministic parity automata can be efficiently minimized under an arbitraryset of don't care words. We derive that from a more general result from whichone also obtains an efficient minimization algorithm for deterministic parityautomata with informative right-congruence (without don't care words).  We then analyze languages of don't care words with a trivialright-congruence. For such sets of don't care words it is known that weakdeterministic B\"uchi automata (WDBA) have a unique minimal automaton that canbe efficiently computed from a given WDBA (Eisinger, Klaedtke 2006). We give acongruence-based characterization of the corresponding minimal WDBA, and showthat the don't care minimization results for WDBA do not extend todeterministic $\omega$-automata with informative right-congruence: for thisclass there is no unique minimal automaton for a given don't care set withtrivial right congruence, and the minimization problem is NP-hard. Finally, weextend an active learning algorithm for WDBA (Maler, Pnueli 1995) to thesetting with an additional set of don't care words with trivialright-congruence.

On Minimization and Learning of Deterministic $\omega$-Automata in the Presence of Don't Care Words