Liveness-automata determinzation

Question

1) For Non-Deterministic liveness automat, when to use subset and when to use breakpoint construction.

As per my understanding, non-deterministic partial liveness automata shall be converted into prefix non-deterministic liveness automata and then use subset construction to determinize, right?

But in slides it is also mentioned that non-deterministic liveness automata will go to non-deterministic co-buchi and then finally into deterministic co-buchi using breakpoint. so in this case, what  shall be used to convert non-deterministic liveness to non-deterministic co-buchi?

I am confused for liveness automat when to use what?

Please explain

TRANSLATE with x

English

Arabic	Hebrew	Polish
Bulgarian	Hindi	Portuguese
Catalan	Hmong Daw	Romanian
Chinese Simplified	Hungarian	Russian
Chinese Traditional	Indonesian	Slovak
Czech	Italian	Slovenian
Danish	Japanese	Spanish
Dutch	Klingon	Swedish
English	Korean	Thai
Estonian	Latvian	Turkish
Finnish	Lithuanian	Ukrainian
French	Malay	Urdu
German	Maltese	Vietnamese
Greek	Norwegian	Welsh
Haitian Creole	Persian

var LanguageMenu; var LanguageMenu_keys=["ar","bg","ca","zh-CHS","zh-CHT","cs","da","nl","en","et","fi","fr","de","el","ht","he","hi","mww","hu","id","it","ja","tlh","ko","lv","lt","ms","mt","no","fa","pl","pt","ro","ru","sk","sl","es","sv","th","tr","uk","ur","vi","cy"]; var LanguageMenu_values=["Arabic","Bulgarian","Catalan","Chinese Simplified","Chinese Traditional","Czech","Danish","Dutch","English","Estonian","Finnish","French","German","Greek","Haitian Creole","Hebrew","Hindi","Hmong Daw","Hungarian","Indonesian","Italian","Japanese","Klingon","Korean","Latvian","Lithuanian","Malay","Maltese","Norwegian","Persian","Polish","Portuguese","Romanian","Russian","Slovak","Slovenian","Spanish","Swedish","Thai","Turkish","Ukrainian","Urdu","Vietnamese","Welsh"]; var LanguageMenu_callback=function(){ }; var LanguageMenu_popupid='__LanguageMenu_popup';

TRANSLATE with

COPY THE URL BELOW

<!--a id="TwitterLink" title="Share on Twitter">

Back

EMBED THE SNIPPET BELOW IN YOUR SITE

Enable collaborative features and customize widget: Bing Webmaster Portal

Back

var intervalId = setInterval(function () { if (MtPopUpList) { LanguageMenu = new MtPopUpList(); var langMenu = document.getElementById(LanguageMenu_popupid); var origLangDiv = document.createElement("div"); origLangDiv.id = "OriginalLanguageDiv"; origLangDiv.innerHTML = "ORIGINAL: "; langMenu.appendChild(origLangDiv); LanguageMenu.Init('LanguageMenu', LanguageMenu_keys, LanguageMenu_values, LanguageMenu_callback, LanguageMenu_popupid); window["LanguageMenu"] = LanguageMenu; clearInterval(intervalId); } }, 1);

Answer 1

Simply proceed as follows:

• If a nondeterministic liveness automaton is totally defined, use the subset construction. That will always work.
• If missing transitions of a partially defined nondeterministic liveness automaton can be added to make it totally defined without changing its accepted language (which is in general not easy to see, but often, it is!), then use the subset construction for the totally defined automaton.
• Otherwise, i.e., if. the partially defined automaton cannot be made total, convert it to an equivalent co-Büchi automaton and use the breakpoint construction.

The third case is unavoidable in some cases, since nondeterministic liveness automata are in general more powerful than the deterministic liveness automata.