`Automata on Infinite Wordsgehalten von Univ.-Prof. Dr. rer. nat. Wolfgang Thomas im Wintersemester 2005/06 an der RWTH Aachen eine studentische Mitschrift von Florian Heller [email protected] Diese Mitschrift erhebt keinen Anspruch auf Richtigkeit oder Vollst¨ ndigkeit. a - Think Different February 7, 20061 Introduction18.10.051.1 The TheoryThe Theory has been formed by Dr. Richard B¨ chi, Trakhtenbrot, Rabin, McNaughton. The subject is the u analysis of finite Automata working on infinite Words.Motivation1. Attractive theory with algorithmic content. 2. Framework to non-terminating reactive systems. 3. Connection to logic (temporal logic and others) A Script of this lecture is available on the website of Informatik 71.2 ExercisesStarting tomorrow. Hand in the Solutions in Groups of three persons.¨ 1.3 Buchi automata and regular -languages Alphabet, B = {0, 1}, a, b, c, . . . letters, u, v, w, . . . finite words,  empty word, + ,   = (0)(1)(2) . . . -Word [over  if (i)  ]  set of -words over  [i . . . j] = (i) . . . ( j) U, V, W, . . . languages of finite words. K, L, . . . languages of -words ¨ Definition (Buchi Automaton) A B¨ chi automaton is of the form A = (Q, , q0 , , F) with finite state set Q, input alphabet , initial state u q0 , transition relation   Q ×  × Q and a set F  Q of accepting (or final) states. accepting -wordby the &quot; B¨ chi condition &quot; u A run of A on  is a sequence  = (0)(1) . . . s.t. (0) = q0 , ((i), (i), (i + 1))   for i  0  satisfies the B¨ chi condition ( accepting) if (i)  F u34 A accepts  if exists run  of A on  wich satisfies the B¨ chi condition u  |Aaccepts} L(A) = {  Example: A0 : a,b a a 2 a 3 1 b aCHAPTER 1. INTRODUCTION = abbababab . . . 1 = 0000000000 . . . 2 = 0000002323 . . . 3 = 0000232323 . . . 2 , 3 accepting. A0 accepts  L(A0 ) = the set of all -words over {a, b} with from some point onwards have ababab . . . or aaaa . . . . Short notation: (a + b) (ab) + (a + b) a &quot;regular expression&quot;Questions1. Reduction to deterministic automata? 2. Alternative characterization of accepted (or recognized) -languages? 3. Closure under operations like ,  4. Algorithmic propertiesIn a deterministic B¨ chi automaton replace  by a transition function  : u Q× Q Then an -word induces a unique run  of A on . (0) = q0 (1) = (q0 , (0)) (2) = ((q0 , (0)), (1)) B¨ chi condition as before. u L1 = {  {a, b} | from some point onwards, in  only a occurs} L2 = {  {a, b} |b occurs only finitely often in} = (a + b) a  Claim: LA is B¨ chi recognizable, but not deterministically B¨ chi rec. u uRemark on determinism Proof: ¨ Assume det. Buchi aut. A recognizes L1 Consider A on aaa . . . . A visits final states infinitely often in its unique run, say first time after n0 letters a. Consider A: an0 baa . . . Next visit to final state is guaranteed by assumption, say after prefix4CHAPTER 1. INTRODUCTIONan0 ban1ConsiderA on an0 ban1 baa . . . Generate infinite word an0 , ban1 ban2 b . . . where the A-run visits final states infinitely often. Contradiction to the assumption on A5¨ 1.4 Towards characterization of Buchi recognizable -languages1.4.1 Preparation· Given U   , define U  = {   | = u0 u1 u2 . . . , ui  U}Example:U = abba + aa U  contains aaabb abba abbaa abbaaa . . .· Given U   , L   , U · L = {   | = u, u  U,   L} Theorem 1 L   is B¨ chi recognizable  L = un i=1 U i· Vi with Ui , Vi   regular.Proof: ¨  Given A = (Q, , q0 , , F) Buchi automaton Define for p, q  Q W p,q = {w   | ex. A-run from p to q via w} W p,q is regular (use (Q, , p, , {q})) Remark: A accepts  if for some q  F  is in Wq0 q · Wqq · Wqq . . . L =qF Wq0 q · Wqq ()Consequence:  is ultimately periodic if  = uvvv . . . for some fixed words u, v Proposition: L B¨ chi recognizable, L   L contains an ultimately periodic -word uProof: Given A, consider the representation () For some q Wq0 q  Wqq  Using u  Wq0 q , v  Wqq find  = uvvv . . .Definition L   is B¨ chi recognizable  L is finite union of sets U · V  , with U, V   regular uProof: Proof of ) Lemma: ¨ a) V   regular  V  Buchi recognizable (B-Rec). b) U   reg, K   B - Rec  L1  L2 B - rec Proof a) Given NFA A = (Q, , q0 , , F) recognizing V Preprocessing: Introduce new initial state q wich cannot be reached via nenempty word, obtain 0 equiv. NFA A ¨ Construct the Buchi-atuomaton B for V  from a· For any transition (p, a, q) with q  F introduce new transition (p, a, q ) 056 · Use {q } as set of final states of B 0CHAPTER 1. INTRODUCTION¨ Proof b) Given NFA A for U , Buchi automaton B for K Introduce over QA  QB for (p, a, q) with q  FA new transistion (p, a, q0B if q0A  FA for (q0B , b, q) new transition (q0A , b, q) Proof c) Given B1 , B2 for L1 , resp L2 Introduce a new initial state q0 and new initial transitionsConsequencepressions) r1 ·s 1B¨ chi-recognizable -languages are described by regular -expressions (-regular exu + · · · + rk · s where ri , si are standard regular expressions. k¨ 1.5 Complementation of Buchi automata.Theorem 2 L   B-rec.   \ L B-recStrategy: Given B¨ chi-automaton A = (Q, , q0 , , F) recognizing L u Define finite family WA = {W1 , . . . , wk } of regular languages Wi   such that · L is finite union of sets U · V  with U, V  A ·  \ L ist also finite union of sets with U, V  A notation (Given A) write p  q[p  q] :  ex run of A on w from p to q [Such than a final state is visited in this run] Definition Given A define for u, v   u A v  for each p, q  Q u v pq pq u v pq pqw wFact 1: A is equivalence relation, call the equivalence classes A -classes [u] Fact 2: Each A -class is regular u u w  [u]  p, q  Q s.t. p  q [not p  q ] w  W pq [w p  q[notp  q] w u uW pq ] and p, q  Q s.t.WF pq(allowing A to go from p to q visiting F )L   B¨ chi-Rec.   \ B¨ chi-Rec. A B¨ chi aut. for L U · V  u u uRemark: From the transition profiles of u, v one can compute the transition profile of uv. Other Formulation:· u a u v a v uv a u v6CHAPTER 1. INTRODUCTION· a is a congruence · U, V  Wa (U, V a classes) U · V  W for some W7Consequence of Lemma 1,2: \ L ={U · V  |U, V  Wa , V · V  V, U · V   L = }Proof (Proof of Lemma 2): Given    Notation [m, n) = (m) . . . (n - 1) Two positions k, k merge at m(&gt; k, k )V k k V  m  V n k  k : k, k merge at some m Remark 1 k, k merge at m, m &lt; n  k, k merge at n: clear from Remark on a being congruence Remark 2  is an equivalence relation over N of finite index.kkkmn Given , by Remark 2, choose infinite  -class, say with k0 , k1 , k2, . . . Consider  = [0, k0 )[k0 , k1 )[k1 , k2 ) . . . Of the segments, [k0 , ki ) infinitely many must belong to fixed a -class, say V So choose a subsequence of the ki , call them k0 , k1 , k2 again, sucht that [0, k0 )  U [k0 , ki )  V for all i &gt; 0 By canncelling some k j we can assume that k0 , ki merge at ki + 1 Call the subsequence obtained again k0 , k1 , . . . Show for this sequence [ki , ki+1  V, i = 0, [k0 , k1 )  V So [ki , ki + 1)  Checkwether U.V  V ¨ complement Buchi automaton we need a test wether U · V   L = For construction ofLemma (Intersection-Lemma:) ¨ ¨ Given Buchi automata a1 , a2 , L(a1 )  L(a2 ) is Buchi-recognizable. ¨ Emptiness Test: Given Buchi aut. a, one can test wether L(a) =  L(a)   ex. final state q, such that · q is reachable from q078 · q is reachable from q by nonempty path.CHAPTER 1. INTRODUCTIONIdea: Given a1 (Q1 , , q01 , 1 , F1 )a2 (Q2 , , q02 , 2 , F2 )construct product automaton Introduce memory component with entries 0, 1, 2:1. wait for state in F1 2. wait for state in F2 3. Cycle completed1.6 Acceptance ConditionsAim: Obtain expressive of NBA by deterministic automata with other acceptance then B¨ chi-ac. u Four basic acceptance conditions (given a = (Q, , q0 , , F))The run   Q is E-Accepting if i, (i)  F A-Accepting if i(i)  F B¨ chi-Accepting if  j i &gt; j, (i)  F u -B¨ chi-acc. , i &gt; j(i)  F uAn E-/A-/B¨ chi/-B¨ chi-cond is here a det. automaton used over -words with E-/A-. . . acceptance u u123a,ba,bError Example:(aa + b) ·   = {a, b}Example:For   Q In f () = {q  Q| ji &gt; j (I) = q}  is visited infinitely often in  Muller aut. has format a = (Q, , q0 , , F), where F = {F1 , . . . , Fk }, Fi  Q8CHAPTER 1. INTRODUCTIONRun  is Muller accepting if In f ()  F i, In f () = Fi L1 set of -words over  = {a, b} with infinitely many b L2 set of -words over  = {a, b} with only finitely many b. ... Lemmaa) The class of Muller recognizable Languages is closed under boolean comb. ¨ b) L is Buchi-recognizable  L is Muller recognizable915.11.05AProof: We show closure under negation (complementation) an  (intersection) Complementation proceed from F toF   qQ \ F Intersection use a product construction, given Ai = (Qi , , qi , i , Fi ), (i = 1, 2) construct A = (Q1 × 0 Q2 , , (q1 , q2 ), , F ) where ((p, q), a)  (1 (p, a), 2 (q, a)) and F defined n, p1 . . . pn  Q1 , q1 . . . , qn  0 0 Q2 : {(p1 , q1 ), . . . , (pn , qn )}  F  {p1 . . . pn }  F1 and {q1 . . . qn }  F2Lemma ¨ ¨ a) L   det. Buchi recognizable   \ L det ca.Buchi recognizableb) L   E-recognizable   \ L is A-recognizable proof of a) (B is similar ¨ Let A = (Q, , q0 , , F) be a det. Buchi automaton with L = L(A)  = (Q, , q , , Q \ F) Define A 0 Then    \ L  In f (  F =   From some point onwards only states from Q \ F are seen , i.e. ¨ i  n (i)  Q \ F  A co-Buchi accepts ¨ Structural Analysis of E- and det. Buchi-recognizable LanguagesLemma a) L   is E-recognizable  L = U wher U   regular¨ b) L   is det. Buchi recognizable  L = lim(U), U  regularDefinition Let u   Lim(u)  {   |[0, . . . , i]  U for inifinitely manyi}Example U = a ba lim(u) = {   | contains exactly one b}Proof: a) Let A = (Q, , q0 , , F) be det. automaton Let L   be the -language E-recognized by A and U   the language recognized by A as finite automaton. Then    isE - AcceptedbyA  in the unique run of A on . Finished after finite prefix u  A accepts u as a finite automaton  u  U and for the remainder of    .910CHAPTER 1. INTRODUCTION¨ b) Let A = (Q, , q0 , , F) det, L = L(A)   Buchi recognized by A, U   reg. language accepted by A as finite DFA. Then for    : Aacceots  in a state from F is visited inf. often i.e.  (i) = q  F for inf. many i  [0, . . . , i] acceptesd by DFA A for inf. many i  [0, . . . , i]  U for inf. manyi    lim(u)Comparison of det. recognizable -LanguagesHierarchy Theorem For the classes of det. E,A,B¨ chi, u co-B¨ chi, Muller-recognizable languages, the following inclusion diagram u All the inclusions are strict! proof strategy: done. B¨ chi  Muller complement Lemma + closure of Muller under boolean comb.  u co-B¨ chi  Muller , we sho E  B¨ chi, E  co-B¨ chi. u u u Then (complement)  A  B¨ chi, A  co-B¨ chi. u u Proof: W  B¨ chi, E  co-B¨ chi u u Let A be an E-automaton recognizing L   We construct automaton A wich both B¨ hi and co-B¨ chi u u  qf recognizes L. A results from A by adding a new accepting sink state, redirtect every transition to a final state in A to q f , i.e. (q, a) = p  F   (q, a) = q f , {q f } = F 22.11.051.6.1 Strict inclusion claimsOn (4): O 1(0 + 1) is not A-recognizable. Assume A with n states recognizes 0 1(0 + 1) A on input 0n 10 accepts, so run has only final states. A : q0  p  p  q On input o the run repeats q0  p  p  p . . . so only final states. A accepts 00ncontradiction. On (5): 0 , complement of 0 1(0 + 1) Assuming {= } is E-recogn., the complement would be A-recognizable. Now use the proof on the language (4). So {0 } is not E-recogn. On(2): L2 = {  {0, 1} | in 101 occurs, but 11 does not } Assume L2 is E-Recognizable, say by A with n states. Consider A on 1010 , reaches a final state, say up to 1010k . On 1010k 1 . A reaches final state and accepts. Contradiction. Assume L2 is A-recognizable, say by A with n states. A accepts 0n 1010 , have state repetitions on prefix 0n , so accept 0 , so contrad. On (7): L7 = {  {0, 1} |1 occurs only finitely often} known: not B¨ chi-recogn. u On (6): L6 is complement of L7 , so it is not co-B¨ chi recognizable. u1.6.2 Deciding the levelsAim: Given Mulller automaton A = (Qm, q0 , , F ) we want to decide wether L(A) is in fact E-recognizable or B¨ chi-recognizable. u10CHAPTER 1. INTRODUCTION11A loop of A is a subset S  Q s.t. for all s, s exists w  + with (s, w) = s over Q  S Remark A set In f () is a loop. We may restrict F to loops only. Assume A has only reacheable states, has acceptance component F containing only loops. F is closed under reacheable then S   F F is closed under superloops  if loop S  F and loop S   S then S   F Remark Given A both properties of F can be checked effectively.1.6.3 Landweber's TheoremLet A be a Muller automaton A = (Q, , q0 , , F ) a) L(A) is E-recognizable if F is closed under reachable loops. b) L(A) is B¨ chi-recognizable if F is closed under superloops. u Proof b)  Assume A is closed under superloops. Construct B¨ chi automaton for L(A) Use set Q × 2Q : u in first component simulate A in second component accumulate visited states until superset S  S  F is reached, then go to  instead (final). Automaton accepts if given aut. A satis f iesIn f ()  S  F  Given Muller-automaton A = (Q, , q0 , a , F ) and a B¨ chi-atuomaton B = (P, , p0 , b , F with L(A) = L(B) u Consider loop S  F , superloop S  . Show S  F Find -word with In f () = S  for the A-run , with A accepts. Start  with prefix w leading A to some q  S . Continue w by  wich causes A to loop through S again and again. B on w visits F-state after w, say adter wu1 . Via word v1 back to q in A, via x1 go once through S in A and back to q. On prefix wu1 v1 x1 A has looped through S  once, B has visited a final state. Repeat the argument with wu1 v1 x1 . Repeateing we Aloops through S  againandagain So B accepts hence accepts, hence S   F obtain wu1 v1 x1 u2 v2 x2 . . . s.t.: B reaches final states inf. often1.7 Weak automataA Staiger-Wagner automaton (weak Muller automaton) has the same format (Q, , q0 , , F ) as Muller automaton, but with the following acceptance: A accepts  if for unique run  of A on : the set of states occuring in  is in F . Occ()  F29.11.200Staiger-Wagner automaton:A = (Q, , q0 , , F ) F  Pow(Q) A accepts   for the unique run  of A in  we have Occ()  F for some F  F , the states of  form F Theorem 3 L   is (det.) B¨ chi- and Co-B¨ chi recognizable  L is Staiger-Wagner recognizable. u uProof:  Given A = (Q, , q0 , , F ) F = {F1 , F2 , . . . , Fk } Construct A over Q × 2Q × · · · × 2Q State (q, R1 , . . . , Rk ) signals that A is in q, and that Ri (i = 1, . . . , k) is the set of states visited sok times1112CHAPTER 1. INTRODUCTIONfar. ¨ Declare (q, R1 , . . . , Rk ) as final if Ri = Fi for some i (For Buchi-automaton A)A visits final inifinitely often  for some i, Ri = Fi infinitely often  for some i, Ri = Fi from some point onwards.¨ ¨ So A used as buchi or as Co-Buchi automaton, accepts if the visited states for A form some Fi .Preparation for : SCC Decomposition) Given transition graph, a strongly connected component is a maximal strongly connected subset. Proposition the SCCs and the singletons wich do not belong to an SCC form a partial ordering under the reachability relation.SCC-Algorithm For directed Graph G = (V, E)1. Run depth-first search, recording enter/farewell-times for the vertices 2. Reverse edges, get GT 3. Run depth-first search on GT , taking as roots of depth-first trees vertices in reversed order of finish times (Starting from vertex with highest farewellResulting d-f-trees are the SCCs (the reacheable vertices form a SCC S of G¨  Given Buchi-automaton wich recognizes L Take Muller-automaton for L, A = (Q, , q0 , , F ) F is closed under superloops. ¨ Since A recognizes a co-Buchi recogn. set, F is closed under subloops. Consequence: All loops of an SCC of A are accepting ( F ) or all loops of SCC are rejecting ( F ). Call SCC S good, if all its loops are accepting, (otherwise it's bad) Fiven S , let S + be the set of states q S with transition (p, q), p  S Consequence: Run  of A is accepting if  reaches some good S but does not reach the correpsonding set S + . So get a Staiger-Wagner-automaton from A with the following acceptance component F  containing a set R  Q if for some good S we have R  S  and R  S + = .122 DeterminizationAim: Transformation of undet. B¨ chi automaton to det. Muller automata. (McNaughton 1966, (Information u and Control)). Safra 1988: Optimal complexity bound for the number of states (Rabin automata) Muller,Schupp (1992): Optimal complexity bound for the number of states a,b b b Problem: Powerset construction is not enough.1...111... infinitely often set visited with fi-nal state 1! Idea of MS-construction: On given input word, build up the &quot;run Tree&quot; of B¨ chi automaton. Use prefixes u of tree up to some level as first approximation of states. Reduction and compression leads to finite number a,b b of states. b a aIllustration with L = (a + b) (b+ a) Example input: Run tree of A = (Q, , q0 , , F) on inputRemark: A accepts   in run tree of A an infinite path exists with infinitely many final states. Reduct1on 1 Put states together if they are final, respectingly nonfinal (final:&quot;down&quot;, vertically display: &quot;left&quot;) Result: Binary branching tree. &quot;Acceptance Tree&quot;. Remark: A accepts   in acceptance of A on  exists path pranching down infinitely often.1314CHAPTER 2. DETERMINIZATIONFrom a nondet. B¨ chi automaton, one can construct an equivalent det. Muller automaton. u Given A = (Q, , q0 , , F), start on input  from run tree of A on  Convention: Branch left(down) with final states.1. Reduction Merge states at a branching when they are final (left succ.) Merge states at a branching when they are non-final (right succ.) Get &quot;acceptance tree&quot; with a most binary branching.Remark: A accepts   in acceptance tree of A on  exists path with infinitley many left turns. easy from condition on run tree  from infinite path in acc. tree obtain a partial run tree wich is infinite and finitely branching.K¨ nigs Lemma gives infinite path of run tree of course with infinitley many left turns. o 2. Reduction On each Level keep only the leftmost (downmost) occurence of each individual state.Remark: A accepts   in the resulted left-reduced acc. tree a path exists with infinitely many left turns.3. Reduction Compress path segments into single nodes:Merge nodes of a path segment into the topmost one (not a successor of branching node) Keep states at leaves, color each node of compressed tree by: · Red: if no final state occurs · yellow: if final state occurs, no final state added · green: if final state was added in left update 4. Reduction Delete all nodes wich do not get a new descendent in the last update step.Result: Muller-Schupp tree (over Q), a finite, strictly binary tree with node names from N+ where node is colored red,green or yellow, and the leaves are labelled with disjoint state sets (over Q). Notation: MS (Q) for the finite set of all Muller-Schupp trees over Q.Remark: A accepts   in the sequence of Muller-Schupp trees of A on , some node stays forever from some point onwards and is colored gren again and again.14CHAPTER 2. DETERMINIZATIONDefinition of Muller automaton A from nondet. B¨ chi automaton A = (Q, , q0 , , F) u 1;red {q0 }15State-set: MS (Q)initial state:Definition of (t, a) (t : MS - tree) using the following update rule: 1. Copy tree, replace green by yellow 2. For each leaf, with state set P, introduce son labelled P = {q|p  P, (p, a, q)  } Delete state p if it occurs more to the left. Split any set into left,right son with the final, resp. nonfinal states with colors green,red. 3. Delete all nodes wich did not get a new descnendant with  set.4. Compress path semgents into the respective top node giving it colour green if it is merged with nodes either coloured green or yellow.Convention about use of node names after deletion step a node name can be reused, however not in an immediate successor tree accordings to update. Observation: Over Q, 3|Q| node names suffices. Acceptance Component: Define F as follows: R( MS (Q))  F  some node name k occurs in each tree of R and even colored green in some tree of R.1; red 1; red2; green Example: t=3; red2; yellow3; red{2}{0, 1} (t, b) to be computed.{0, 1, 2}1; red 1; red 2; yellow 3; red 4; green 5; yellow 4; green 5; red{2}{0, 1}{2}{0, 1}Definition Define Ek  set of MS-trees without node k Fk  set of MS-trees with node k colored green. Acceptance Condition: for some k: any tree in Ek occurs only finitely often, some tree in Fk occurs1516 infinitely often. Start notation for run  (of MS-trees):CHAPTER 2. DETERMINIZATIONm k=1In f ()  Ek =   In f ()  FkDefinition A (det.) Rabin-automaton has the form A = (Q, , q0 , , ) where  is sequence (E1 , F1 ), . . . , (Em , Fm ) of sets  Q. A-run  is accepting if for some k  {1, . . . , m}: In f ()  Ek =   In f ()  Fk  13.12.05 Theorem 4 A nondet. B¨ chi aut. can be transformed into a deterministic Muller automaton and also into u a det. Rabin automaton. Rabin aut.: A = (Q, , q0 , , )  = (E1 , F1 ), . . . , (Em , Fm )) Ei , Fi  Q  successfull  m (In f ()  Ei =   In f ()  Fi ) i=1 Remark on Rabin and (Union Lemma) Given Rabin aut. over Q, whith  = (E1 , F1 ), . . . , (Em , Fm )), 1 , 2 non-successful runs Let  be run with In f () = In f (1 )  In f (2 )  is not successfulProof:1 , 2 arenotsuccess f ul, assume  is successful, In f () = In f (1 )  In f (2 ) Pick index i: In f ()  Ei =   In f ()  Fi  Then In f ()  Ei = , In f (2 )  Ei =  Also In f (1 )  Fi  or In f (2 )  Fi  So 1 or 2 successful Theorem 5 MS-construction yelds a Rabin automaton with 2O(nlog n) states from B¨ chi automaton with n u statesProof: Estimate number of MS-Trees over Q, |Q| = n MS-trees are built from node names 1, . . . , 3n Fix a MS-Tree by the following functions:parentp : N  N  {0, }   parent if exists      p(n) = 0 i k is root      otherwise right brother rb : N  N  {0, } anologously color: c : N  {green, red,yellow}  {} State occurence:Q  N  {0}   : node where q occurs if q occurs    0  otherwise  (3n + 2)3n · (3n + 2)3n · 43n · (3n + 1)n  (4n)10n = 2O(n log n)Number od MS-Trees  number of quadruples (p, rb, c, ) of functions.Optimality of bound:16CHAPTER 2. DETERMINIZATION17Theorem 6 There is Ln  {#, 1, . . . , n} recognized by B¨ chi aut. with n + 2 states auch that any det. Rabin u =(n log n) automaton recognizing Ln needs  n! states. n!  2Proof: ¨ Buchi automaton for Ln  = {#, 1, . . . , n}q0 #1###1 3 2 13 4nfCycle property:   Ln  exists letters i1 , . . . , ik   \ {#} such that the letter paris segments i1 i2 , i2 i3 , i3 i4 . . . ik-1 ik , ik i1 occur infinitely often.Consider permutation (i1 , . . . , in ) of 1, . . . , n (i1 , i2 , . . . , in #) Ln Assume A does not accept (i1 , . . . , in #) , ( j1 , . . . , jn #) with permutations i1 , . . . , in j1 , . . . , jn The runs  ,  of A on , resp  are not successful, In f ( ) = R Show; In f ( ) = S R  S =  So A has  n! states. Assume q  R  S . Build -word with infinitely many occ. of i1 . . . in , j1 . . . jn In f () = R  S ,  not successful.i1 . . . ik j1 . . . jkget cycle in input word. Contradiction!173 Monadic Theory of one successor (S1S)We consider transition systems.P1 P1 , P2 P2 pi denote properties of the states arrows = possible behaviour of the system. Associate boolean vector to properties1 0 1 1 0 10 0pi is true  i-th component is 1 Execution of such a system yields an -word over Bm  eg:  = 1 1 0 1 0 1 0 1 0 0 evolvement of single property over time is the projection to the corresponding row Express specifiication for the behaviour of the system by expressing specification for -words over Bn Use S1S for this: variables si t . . . for time points, positions variables X, Y, Z . . . sets of positions, 0 constant, successor  &lt; earlier, = , + boolean connectors + quantificationExample: Constant: At position 3, p1 holds. (X1 ) = X1 ( 0 )=3Reactivity: Sometimes p1 holds. 2 (X1 ) = tX1 (t) Recurrence: again and again p1 holds: ts &gt; t : X1 (s) Request - Response: Whenever p1 holds, p2 holds afterwards.s(X1 (s)  t(t &gt; s  X2 (t))18CHAPTER 3. MONADIC THEORY OF ONE SUCCESSOR (S1S)193.1 Formal SyntaxVariables: s, t, . . . Second-order variables: X, Y, X1 , X2 . . . Terms: constant 0, first-order variables,  term   term Atomic formulas: X(),  &lt; ,  =  with ,  terms. S1S-formulas are obtained from the atomic formulas by using boolean connectives and quantification.3.2 SemanticsUse N as universe for first-order variables Use 2N as universe for second-order variables The interpretation of  is +1 &lt;= less than on N Use standard semanticsWrite(N, 0, +1, &lt;, P1 , . . . , Pn ) (X1 . . . Xn ) where X1 . . . Xn are the free variables od  if  is true in these semantics if the free variable Xi is interpreted as Pi ¯ We need to specify only P1 . . . Pn = P ¯ For P1 . . . Pn  N we define (P)(  (Bn ) by ((i)9 j = 1 iff i  P j ¯ Then we write (P) (X1 . . . Xn Definition  For S1S-formula (X1 . . . Xn ) define L() = {  ((B)n | (X1 . . . Xn )} 20.12.05¨ 3.2.1 Connection from S1S to Buchi-automataS1S: s, t, . . . positions of -words. X, Y, . . .sets of positions 0, , &lt;X(s) &quot;Monadic second-order logic&quot; X(s ) ¬, , , , , ,  Formula (X1 , . . . , Xn ) satisfied in a model (N, 0, , &lt;, P1 , . . . , Pn )  -word over {0, 1}Example (for correspondance (p1 , P2 )  {0, 1}2 ):P1 even numbers: 1 0 1 0 1 0 1 0 1 0 . . . P2 prime numbers: 0 0 1 0 1 0 1 0 . . . (X1 , X2 &quot;There are two successive positions with 1 in second component followed by 1 in first component&quot;1920With  from above: CHAPTER 3. MONADIC THEORY OF ONE SUCCESSOR (S1S)st(s = t  X2 (s)  X2 (t)  X1 (t )) s(X2 (s)  X2 (s )  X1 (s )) L  {0, 1}n S1S-definable  exists S1S-formula (X1 , . . . , Xn ) s, t for any   ({0, 1}n ) :   L   (X1 , . . . , Xn ) Theorem 7 (B¨ chi 1960) An -language L  ({0, 1}n ) is S1S-definable if and only if is B¨ chi-recognizable. u uProof: ¨ []: Given Buchi-automaton 1q10q20q30 = {0, 1} Find (X) saying &quot;A accepts the -word corresponding to X &quot; (X) has to say: exists a successful run of A over  corresponding to X  = 1 0 1 0 0 0 0 q1 * * q2 * * q3 * * 0Idea: Express existence of run by existence of three set Y1 , Y2 , Y3 Express that Y1 , Y2 , Y3 represents successful run (X) : Y1 , Y2 Y3 ( each position belongs to singly Yi Y1 (0)s(Y1 (s) X(s)Y2 (s ))(Y2 (s)¬X(s)  Y1 (s )) (Y2 (s)  ¬X(s)  Y3 (s ))  (Y3 (s)  ¬X(s)  Y3 (s ))] st(s &lt; t  Y3 (t))) General Case A = (Q, {0, 1}n , q1 , , F) Q = {q1 , . . . , qm } (X1 , . . . , Xn ) : Y1 . . . Ym (Partition(Y1 , . . . Ym )Y1 (0) s (qi ,a,q j  (Yi (s)Xa (s)Y j (s))st(s &lt; t  qi F Yi (t)) Partition (Y1 , . . . , Ym ) :  m Yi (s)  ¬s i j (Yi (s)  Y j (s)) i=1  empty bi = 1   For a = (b1 , . . . , bn ) b1  {0, 1} write Xa (s) for (b1 )X1 (s)· · ·(bn )Xn (s) where bi =  ¬  bi = 0 ¨ [] From S1S-Formulas to buchi-automataSimplify formalism S1S to S1S0 with second order variables only. S1S0 has new atomic formulas : S ing(X) for &quot;X is a singleton&quot; S ucc(X, Y) for X = {s}, Y = {t} with s = tXYLemma S1S formulas can be rewritten as S1S0 -formulas Proof Apply the following steps: Eliminate 0: X(=) s(X(s)  tt = s) Eliminate iterations of  X(s ) t(s = t  X(t )) Eliminate &lt;: s &lt; t &quot;t is in successor closure of s &quot; X(X(s )  z(X(z)  X(z ))  X(t)) Get S1S-formulas with atomic formulas s = t X(s) only From such formulas obtain an equivalent S1S0 formula. Example: Xst(s = t , X(s)) XS (S ing(S )  T (S ing(T )S ucc(T, S )S  X) Lemma Each S1S0 formula (X1 , . . . , Xn )canbe ¨ transformed into an equivalent Buchi-automaton. Proof by induction on S!S0 -formulas.20CHAPTER 3. MONADIC THEORY OF ONE SUCCESSOR (S1S)0 1 Atomic formulas0 0 S ing(X1 ) 1 0 0 12100 0S ucc(X1 , X2 )X1  X2For induction step assume that only connectives ¬   remain (, ,  have been eliminated) ¨ ¬ Consider ¬(X1 , . . . Xm ), assume by ind Buchi automaton A for  ¨ Use Buchi-aut. complementation to find automaton for ¬ ¨ : 1 (X1 . . . )2 (X1 . . . ), assuming Buchi aut. A1 , A2 . Use union automation of A1 , A2 ¨  Consider X(X1 , . . . , Xm , X) assuming Buchi-aut. A over {0, 1}m+1 Find autom. over {0, 1}m 11 0 0 0 10 1 Example: (X1 , X) New automaton reads only first component ans messes second comp. with this simulating given automaton. 10 Implementation: Delete second components in the given automaton:10.1.06¨ From S1S-formulas to Buchi-automaton(X1 , . . . , Xn )  A over  = {0, 1}n such that for each  (X1 , . . . , Xn )  A accepts ({0, 1}n )(X1 ) : s(X1 (s)  ¬X1 (s )) First Step: Rewriting as S1S0 -Formula: st(X1 (s)  s = t  ¬X1 (t)) X2 X3 (X2  X1  S ucc(X2 , X3 )  ¬X3  X1 )Illustration(X1 ,X2 ,X3 )2122CHAPTER 3. MONADIC THEORY OF ONE SUCCESSOR (S1S)X2 = {s}, X3 = {t} Automaton for X2  X1  S ucc(X2 , X3 )(1,1,0)(0,0,1) (0/1,0,0)(0/1,0,0,) For intersection with ¬X3  X1 take only (0,0,1) at () Automaton for full formula: forget 2nd / 3rd component.1st Step Theorem 8 For each S1S-formula (X1 , . . . Xn ) one can construct an equivalent B¨ chi-automaton over  = u{0, 1}n , and converselyRecall: Given B¨ chi automaton, an equivalent formula can be written as Y1 . . . Ym (X1 , . . . , Xm , Y1 , . . . Ym ) uf irst Order() Consequence 1: Call S1S-formula existential if it has form () Each S1S-formula (X1 . . . Xn ) is equivalent to an existential one. Proof by translation:   A  formula equivalent to A (of the form ()) existential. Consequence 2: Decidability of aritmetical theorics Use Theorem for n = 0, i.e. for sentences  (without free variables). A has unlabelled transitions. (N, , &lt;, 0)   A has a successful run (state sequence with infenitely many visits of final state) Hence: For each S1S-sentence one can decide whether it is true in (N, m, &lt;, 0)Example: stt &lt; s false (take s=0)X (X(0)  s(X(s)  X(s ))  tX(t)) (induction princ.) True &quot;The monadic second-order theory of (N, , &lt;, 0) is decidable&quot;¨ Background: Godel's result on &quot;undecidability&quot; of first-order arithmetic (for the structure (N, +, ·, 0, 1, &lt;) Example:x(x &lt; y  z1 z(z1 · z2 = y  z1 = 1  z2 = 1)y is primeThere are infinitely many primes.xy(x &lt; y  y is prime  y + 1 + 1 is prime &quot;There are inifinitely many twin primes.&quot;Remark: ¨ Remak (Godel): The full second-order theory (with quantification over relations) of (N, , &lt;, 0) is undecidable. Proof: By second-order definitions of + ans  x + y = z  each relation wich contains (0, x) and is closed under successor in both components mus contain (y, z) R((0, x)  R  (s, t)((s, t)  R  (s , t )  R)  (y, z)  R) x · y = z analogously, using +22CHAPTER 3. MONADIC THEORY OF ONE SUCCESSOR (S1S)Decidability?23(Tarstei) What about &quot;monadic quantification&quot;? (Quantifiers over sets only) Solution byB¨ chi. u T h(N, +, &lt;, 0, 1) T h(N, ·, &lt;, 0, 1) decidable (Presburger, Skolem) Consequence 3 Monadic theory of a structure (N, , &lt;, 0, P) with some fixed P  NExample: P= set of primesst(s &lt; t  P(t)  P(t )) twin prime statement.Question: For wich P is the monadic theory decidable. Approach: Use B¨ chi's theorem about (X)  A u for a fixed set/sequence P.  1 i  P   Given , find B¨ chi A such that (N, , &lt;, 0, P)   A accepts  p  p (i) =  u 0 i P  P primes: 001101010001 dotsExample: ¨ For P = primes st(s &lt; t  P(t)  P(t )) is true  the following Buchi automaton accepts P 0,1 1 1 0¨ MT h(N, , &lt;, 0, P) is decidable if the following decision problem is decidable: Given Buchi-automaton over  = {0, 1} Does A accept PConsequence 4: Method for model-checking. Basic situation: P :Program (System) given as transition graph. Here:represented as a (B¨ chi) automaton (with all states final) u Specification: S :Formula about the desired system runs. Here: S1S formula about the transition labels. P is corrext with respect to S: all runs wich are possible in P satisfy S L(A p )  L(AS ), equivalently L(A p  L(A)S = 17.01.062324CHAPTER 3. MONADIC THEORY OF ONE SUCCESSOR (S1S)3.3 The binary Tree and the two-dimensional Grid1 2 3 .... . .. . .. . .Format of binary tree: ({0, 1} , succ0 , succ1 , ) succ0 (w) = w0 and succ1 (w) = w1 Introduce monadic second order language as before with succ0 , succ1 instead of  . S 2S is the corresponding logical system. Theorem 9 (Rabin, 1969) MT h({0, 1} , succ0 , succ1 , ) is decidable.Format of the grid: G2 = (N × N, succ1 , succ2 , (0, 0)) succ1 (x, y) = (x + 1, y) succ2 (x, y) = (x, y + 1) Theorem 10 (Seese, 1975) Mth(G2 ) is undecidableProof: Use reduction of the halting problem for Turing machines. Task: Given TM M , construct sentence  M s.t. M halts started on empty tape  G2  M Use TM on left-bounded tape TM-computation is sequence of configurations C0 , C1 , C2 , . . . Convention: Repeat halting configuration Halting signalled by &quot;stop state&quot; qs Idea Express existence of halting computing computation of M by requiring a corresponding labelling C0 q0     . . . q0  1Rq1 od G2 C1 1 q1    . . . q1  1Nq0 C2 1 q0 1   . . . For construction of  M use work-alphabet {a0 , . . . , an } and M -states q0 , . . . , qk Introduce X0 , . . . , Xn , Y1 , . . . , Yk Xi = set of positions where ai occurs Y j = set of positions where q j occurs  M : X0 , . . . , Xn Y1 , . . . , Yk (Partition (X0 , . . . , Yk ) + &quot;first row corresponding to inital conf. (empty tape)&quot; [Y0 (0, 0)  y(S 2 ((0, 0), y)  X0 (y))]  &quot;each successor row corresponds to successor configuration of preceeding row&quot;xYk (x)For () with down condition on 2 × 4 boxes of grid. q0 1 q1 Because the Turing Maching is 24CHAPTER 3. MONADIC THEORY OF ONE SUCCESSOR (S1S)25deterministic: For each labelling wich starts in the first row and wich continues in admissible windows, a stop state will be reached.254 Model-Checking and Temporal LogicsModel-Checking-Problem:Given Structure/System S YS , specification S PEC . Does S YS satisfy S PEC? Plan: Formalisation/ automata-theoric approach.1. Kripke structures as system models 2. Basic specifications 3. Formal specification languages (exp. k times), non elementary [S 1S ]: model-checking is very hard(O(2)2 Introduce temporal logic LT L, show that M.C. is PSPACE-complete 4. Use automata to solve the m.c. problem2 2...1. Kripke Structures: Let p1 . . . pn atomic propositions (base &quot;state properties&quot;) A Kripke structure over p1 . . . pn is a tuple M = (S , R, ) where · S is a finite set of &quot;states&quot; · R is a transition relation, R  S × S ((s1 , s2  R: the system can go from s1 to state s2 ) ·  is a &quot;labelling function&quot;,  : S  S p1 ...pn · pi  (S ): the base property pi is true at state s. Example: traffic light, three atomic propositions: p1  red light is on p2  yellow light is on p3  green light is on p1 , p2 p2 1 S1 S2 p3 S4 Notations: a) A pointed K.S. is a K.S. M = (S , R, ) with an initial state s  S S326CHAPTER 4. MODEL-CHECKING AND TEMPORAL LOGICS     n :  b) Usually, we write (s) as a bit vector  (B)      c) Convention we don't allow... b1 . . . bn        : bi = 1 iff pi  (S )     27Definition 1) A Path through a K.S. M = (S , Q, )(M, S ) is an inifinite sequence of states s0 , s1 , s2 . . . with: s0 = s (si , si+1 )  R for all i  N 2) Label sequences for a path s0 s1 s2 . . . is the -word (s0 )(s1 ) . . . 3) The language of (M, S ) is the set of label sequences of paths through (M, S ), we write L(M, s)  (B)Model-checking Problem revisited: Given a Kripke structure (M, S ) over p1 . . . pn , and a specification  on -words over , does every path through (M, S ) satisfy ? L(M, S )  L()? 24.01.06Model-Checking-Problem: Given Kripke-structure specification:Logical formula (M, s) ? Does (M, s) satisfy ?Review1 0 1 1 0 00 1L(M, s) Label sequence:1 1 0 1 0 0 1 0 1 0 0 0...Approach for solution:Construct B¨ chi automata AM,s for L(M, s) and A for L() u and check wether L(AM,s )  L(A ) Formulation of  given often in &quot;linear time temporal logic&quot; LTL (in fact, subsystem of S1S).Plan: Introduce LTL Sketch translation from LTL  B¨ chi aut. u Solve MC Problem2728CHAPTER 4. MODEL-CHECKING AND TEMPORAL LOGICS4.0.1 LTLBasic sequence properties (over two state properties p1 , p2 ) Guaranteed property: &quot;sometime p1 becomes true&quot; (E-aut.) [F p1 ] Safety property: &quot;alwys p1 is true&quot; (A-aut.) [G p1 ] Periodicity property: &quot;Initially p1 is trie , and p1 is true precisely every third moment.&quot; (A-aut.) [p1  X¬p1  XX¬p1  G(p1  XXX p1 )] Obligation property: &quot;Sometimes p1 is true, and p2 is never true&quot; (SW-aut.) [F p1  ¬F p2  F p1  G¬p2 ] Recurrence property: &quot;Again and again, p1 is true&quot; (B¨ chi-condition) [GF p1 ] u Request-response property: &quot;Always when p1 holds, then sometime later p2 holds&quot; [G(p1  XF p2 ] Until property: &quot;Always when p1 holds, sometime later p1 holds and in the meantime p2 holds&quot;. [G(p1  X(p2 U p1 ))] Fariness property: &quot;If p1 is true again and again, so is p2 &quot; [GF p1  GF p2 ]Fomalisations with temporal operators:X &quot;next&quot; G &quot;always&quot;F &quot;sometimes&quot; U &quot;until&quot;Remark: ¨ All formulas can be expressed by Buchi automata over {0, 1}21 ·0 ·Periodicity:1 00 ·· 0obligtion: recurrence:0 01 · 1 · 0 ·0 ·28CHAPTER 4. MODEL-CHECKING AND TEMPORAL LOGICSLTL-Syntax29LTL-formulas over p1 . . . pn are defined inductively as follows: · pi ist LTL formula (i = 1, . . . , n) · If ,  are LTL-formulas, then also ¬,   ,   ,   ,    [¬,  ] suffices · If ,  are LTL-formulas, then also X F G U In -sequences over  = {0, 1}n Notation: For   ({0, 1}n ) ,  = (0)(1) · · · i = (i)(i + 1)(i + 2) . . . ((i)) j = j-th component of (i) Satisfaction relation &quot;i &quot; is defined inductively: i p j  ((i)) j = 1 i ¬  not i  similarly for , ,  i X  i+1  i F   j  i  j  i G  f orall j  i  j  i U   j  i( j   k(i  k &lt; j  k ))Example:GF p1 (00  GF p1 F p1k  j  0 j   jk  j p1((k))1 =1 infinitely often p1 is trueEvaluation of LTL-formulas : F(¬p1  X(¬p2 U p1 )) = ¬p1 ¬p2 -Expension of  ¬p2 U p1 X(¬p2 U p1 ¬p1  X(¬p2 U p1 ) F(¬p1  X(¬p2 U p1 ))1 0 0 1 1 1 0 0 1 0 0 1 0 1 0 10 1 1 0 0 11 0 0 1 1 10 0 1 1 0 11 1 1 1 1 10 1 1 0 0 01 0 0 0 0 01 0 0 0 0 01 0 0 0 0 0... ... ... ... ... ... ...Theorem 11 (Main Theorem) An LTL formula  over p1 . . . pn can be transformed into a B¨ chi automaton u A over  = {0, 1}n such that for all       A can be constructed with state set {q0 }  {0, 1}m31.01.062930Idea:CHAPTER 4. MODEL-CHECKING AND TEMPORAL LOGICSDeclare the bit vectors for truth of subformulas as states of B¨ chi automaton u Technical Preparation:a) tt : p1  ¬p1 f f : p1  ¬p1 F : ttU G : ¬F¬ Temp op. X, U suffices.b) U    (  X(U)) c) Generalized B¨ chi automaton: A = (Q, , q0 , , F1 , . . . , Fk ) u A accepts   exists run of A ond  such that each Fi (i = 1, . . . , k) is visited infinitely often. Lemma (Translation Lemma) Any LTL formula  over p1 . . . pn wih temporal operators X, U only and with m subformulas 1 . . . m ( ¨ pi ) can be transformed into a generalized Buchi-automaton with state set {q0 }  {0, 1}m Aim: Automaton has a unique successful run, namely the sequence of truth-value vectors for 1 . . . n7.2.06Given , subformulas 1 , . . . , m of , the -expansion of  satisfies the compatibility conditions:  j = ¬ j1 : ((i)) j = 1  ((i)) j1 = 0  j =  j1   j2 : ((i)) j = 1  ((i)) j1 or (i)) j2 = 1  j = X j1 : ((i)) j = 1  ((i + 1)) j1 = 1  j =  j1 U j2 : ((i)) j = 1  ((i)) j2 = 1  (((i)) j1 = 1  (((i)) j2 = 0 in the last case (U-Formula): there is no k s.t. for i &gt; k ((i)) j = 1 but ((i)) j2 = 0.¨ 4.0.2 LTL  Buchi automataComaprison LTL - FO (first order logic over -words)Example:G(p1  X(p2 U p1 )) p1 at time x  X1 (x) s (X1 (s)  t (s &lt; t  X1 (t)  r(s &lt; r &lt; t  X2 (r))) Theorem 12 LTL and FO are of same expressive Power.Proof: LTL  FO: easy by induction FO  LTL: Difficult. (superexponential blowup in formula length) Intuition: FO-Quantification can be restricted to intervals [s, t] (r(s &lt; r &lt; t  . . . )) Illustration for LTL: p1  X(p2  F p3 )U p1 )Theorem 13 a) An LTL-formula with m distinct subformulas can be translated into a B¨ chi automaton u with O(2m ) states.   2m      . states b) An FO-formula with m connectives is translatable to B¨ chi aut with m  u  ..     2 30CHAPTER 4. MODEL-CHECKING AND TEMPORAL LOGICS¨ Translation LTL  Buchi automata31via alternating B¨ chi automata (ABA) u Idea of alternating automaton: Allow existential (or-) branching as in nondet. aut. and universal (and-) branching.a a bq0q1q2a,bb Example: Run tree on inputbabbaab... q0 q0q0q0q0q0q0q0 q1q0 ff q2q1q2q2q2...Nondetdermin-ism generates different run trees (for each nondet. choice a new run tree). ¨ Alt. Buchi automaton accepts  iff exists run tree on  such that all branches of it are successful (end in tt or visit final state inifinitely often)Theorem 14 An LTL-formula can be translated into an Alt. B¨ chi automaton where the set of states is the u set of subformulas (with f f, tt)IllustrationFG¬p1 (input alphabet:  = {0, 1}) 0 0 0 1 1 ffFG¬p1G¬P1tt3132CHAPTER 4. MODEL-CHECKING AND TEMPORAL LOGICS000000...Transformation of ABA into standard B¨ chi automaton u As states use sets of ABA-states, updated according to the growth of ABA run tree(s) Comparison of LTL (or FO) with B¨ chi automata (or S1S) uSecond Step:Theorem 15 B¨ chi automata are strictly more expressive then LTL uExample:L0 = (00) 1 is not LTL-definable.q00 01q31q1 L = (10) 1 is LTL-definable.Proof: Proof strategy· Introduce property &quot;non-counting&quot; for -languages L · Show that each LTL-def -language has this property · L0 = (00) 1 violoates this property L   : for sufficiently large n: xy xyn   L  xyn+1   L Negation: L &quot;counting&quot;: there are inifinitely many n and xy sucht that xyn   L, x, yn+1 conversely. L0 is counting: take any even n, x = , y = 0,  = 1 (oo) 1 : xyn   L0 , xyn+1  L0L or32CHAPTER 4. MODEL-CHECKING AND TEMPORAL LOGICS334.1 Beyond reular -languagesScale of complexity for -languages: Level 1: -languages of form L = W ·    L  ex.  prefix in W, W   Level 2: -languages of form L = limW (W   ) General construction: Borel hierarchyLevel 1 1 class of L = W ·  with W   1 : class of complements of 1 -languages Level (n+1) (n+1) : class of countable unions i Li with Li  n n+1 class of countable intersections i Li with Li  n Remark: 2 = class of languages limW33Contents1 Introduction 31.1 1.2 1.3 1.4 1.5 1.61.72 3The Theory . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . B¨ chi automata and regular -languages . . . . . . . . . . . u Towards characterization of B¨ chi recognizable -languages u 1.4.1 Preparation . . . . . . . . . . . . . . . . . . . . . . Complementation of B¨ chi automata. . . . . . . . . . . . . u Acceptance Conditions . . . . . . . . . . . . . . . . . . . . 1.6.1 Strict inclusion claims . . . . . . . . . . . . . . . . 1.6.2 Deciding the levels . . . . . . . . . . . . . . . . . . 1.6.3 Landweber's Theorem . . . . . . . . . . . . . . . . Weak automata . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .3 3 3 5 5 6 8 10 10 11 1113 18Determinization Monadic Theory of one successor (S1S)3.1 3.2 3.34Formal Syntax . . . . . . . . . . . . . . . . . . . Semantics . . . . . . . . . . . . . . . . . . . . . 3.2.1 Connection from S1S to B¨ chi-automata u The binary Tree and the two-dimensional Grid . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .. . . .19 19 19 2426Model-Checking and Temporal Logics4.14.0.1 LTL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.0.2 LTL  B¨ chi automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 u Beyond reular -languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3334`

34 pages

#### Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

927653