[PDF] [PDF] SYNCHRONISING AUTOMATA AND A CONJECTURE OFˇCERN´Y

[PDF] Homework 2 Solutions

23 mar 2017 · Find a regular expression for the set {anbm : (n + m) is odd} Answer There are two cases: • n is even and m is odd: (aa)∗b(bb) 

[PDF] Homework 1 Solutions

8 mar 2016 · Find grammars for Σ = {a, b} that generate the sets of (a) all strings with For Σ = {a, b}, construct dfa's that accept the sets consisting of all the strings with Find minimal dfa for the Language L = {anb : n ≥ 0}∪{bna : n ≥ 1}

[PDF] proving languages not regular using Pumping Lemma

The Pumping Lemma is used for proving that a language is not regular Here is the To prove that a language L is not regular, we use proof by contradiction Here are the steps A wrong choice here will make step 4 impossible 4 By Pumping Combining with (ii) — depending on whether uv is even or odd, v is some 

[PDF] SYNCHRONISING AUTOMATA AND A CONJECTURE OFˇCERN´Y

phabet {0,1} containing an odd number of instances of the letter 1 19 1 5 The subset transition graph of the automaton featured in figure 1 4 28 The set ∪n ≥0Σn of all finite words over an alphabet Σ is denoted by Σ∗ (NB the known as a regular expression, and demonstrated a correspondence between regular

51 How to find probabilities 52 Computations with probabilities 53

5 7 Decision analysis: Using probabilities to make decisions From the questions on page 177, you can see that the word probability value, the probability is 0 15 that the sample standard deviation is less Odds are given in whole numbers, like 4 to 9, for ease in expression is n, b of one kind and r of the other kind

[PDF] PROBABILITY & STATISTICS

Each object in a set is called an element of the set ▫ Mathematically, the probability that an event will occur is expressed she might find that the probability that a visitor makes a purchase given that an odd number has been obtained, is equal to 1/3 as The normal distribution is a symmetric distribution with well-

[PDF] Sampling Distributions - Macmillan Learning

it would be very unusual to get a pˆ value this small when p = 0 50 Imagine taking a random sample of 50 M&M'S® Milk Chocolate Candies Make a graph ment we can make to the formula for σpˆ that correctly reduces the standard devi- ation and 1000 SRSs of size nB = 8 from an approximately Normally distributed

[PDF] find a regular expression for the set {anbm:( n + m) is even}.

[PDF] find a regular grammar that generates the language l (aa* (ab+ a)*).

[PDF] find all complex solutions calculator

[PDF] find an inmate

[PDF] find coinbase account number

[PDF] find connected components in directed graph

[PDF] find death notices

[PDF] find degree of vertex in graph

[PDF] find my 1099 misc online

[PDF] find my twitter account

[PDF] find object type javascript

[PDF] find octagonal prism volume

[PDF] find perfect square trinomial calculator

[PDF] find the basic feasible solution

[PDF] find the density of seawater at a depth where the pressure is

SYNCHRONISING AUTOMATA AND A

CONJECTURE OF

CERN´Y

A dissertation submitted to the University of Manchester for the degree of Master of Science in the Faculty of Engineering and Physical Sciences 2008

Peter John Walker

School of Mathematics

ContentsAbstract7

Declaration8

Copyright Statement9

Acknowledgements10

1 Introduction11

1.1 Overview of content . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2 Notation, concepts and definitions . . . . . . . . . . . . . . . . . . .. 14

1.2.1 Input sequences and languages . . . . . . . . . . . . . . . . . . 14

1.2.2 Finite state automata . . . . . . . . . . . . . . . . . . . . . . . 15

1.2.3 Characterisations of automata . . . . . . . . . . . . . . . . . . 18

1.2.4 Subset transition graphs . . . . . . . . . . . . . . . . . . . . . 26

1.3

Cern´y"s conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291.3.1Cern´y"s examples . . . . . . . . . . . . . . . . . . . . . . . . . 30

1.3.2 A crude bound . . . . . . . . . . . . . . . . . . . . . . . . . . 33

1.3.3 Strongly connected automata . . . . . . . . . . . . . . . . . . 34

1.3.4 Evidence for the conjecture . . . . . . . . . . . . . . . . . . . 37

2 Some partial results41

2.1 Circular automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.1.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2

2.1.3 Pin"s Theorem on circular automata with a prime numberof

states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.1.4 The generalised case of circular automata (Dubuc) . . . . .. 44

2.2 Monotonic automata . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.2.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.2.3 The monotonic interval automaton . . . . . . . . . . . . . . . 46

2.2.4 The

Cern´y conjecture for monotonic automata . . . . . . . . . 47

2.2.5 Monotonic automata with a linear ordering . . . . . . . . . .. 49

2.3 Aperiodic automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.3.2 Almost minimal simply connected components . . . . . . . . . 52

2.3.3 The

Cern´y conjecture for aperiodic automata . . . . . . . . . 57

2.4 Automata with Eulerian state transition graphs . . . . . . . . . .. . 59

2.4.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.4.2 Linear transformations of states . . . . . . . . . . . . . . . . . 60

2.4.3 Thecardinality-changetransformation . . . . . . . . . . . . . 62

2.4.4 The

Cern´y conjecture for Eulerian automata . . . . . . . . . . 62

3 Algorithms for synchronising automata 65

3.1 Pairwise synchronisation of states . . . . . . . . . . . . . . . . . . . . 65

3.2 Natarajan"s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.2.2 Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.2.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.3 Eppstein"s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3.3.1 Preprocessing stage . . . . . . . . . . . . . . . . . . . . . . . . 69

3.3.2 Description and properties . . . . . . . . . . . . . . . . . . . . 73

3.4 Roman"s algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

3.4.1 Preliminary definitions . . . . . . . . . . . . . . . . . . . . . . 74

3

3.4.2 Prioritising synchronisations . . . . . . . . . . . . . . . . . . . 763.4.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773.4.4 Complexity of Roman"s Algorithms . . . . . . . . . . . . . . . 79

3.5 Difficulty in finding minimal reset words . . . . . . . . . . . . . . . .81

3.5.1 Encoding an automaton . . . . . . . . . . . . . . . . . . . . . 81

3.5.2 Encoding of input words . . . . . . . . . . . . . . . . . . . . . 83

3.5.3NP-completeness of the synchronisability problem . . . . . . 84

4 Bounds on the length of a synchronising word 93

4.1 A cubic bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

4.2 Some improved cubic bounds . . . . . . . . . . . . . . . . . . . . . . 94

4.3 The best known bound . . . . . . . . . . . . . . . . . . . . . . . . . . 94

4.3.1 A combinatorial problem . . . . . . . . . . . . . . . . . . . . . 95

5 In pursuit of new results98

5.1 Improving on Pin"s bound . . . . . . . . . . . . . . . . . . . . . . . . 98

5.1.1 The notion of anefficientdescent . . . . . . . . . . . . . . . . 99

5.2 The extensibility of Trahtman"s theorem for aperiodic automata . . . 102

Bibliography106

Word count 23,161

4

List of Figures

1.1 A finite state automaton viewed as a scanning machine . . . . . .. . 18

1.2 The state diagram of an automaton accepting all words overthe al-

phabet{0,1}containing an odd number of instances of the letter 1 . 19

1.3 Three simple automata designed to accept the empty set, the empty

word, and the singleton worda, respectively . . . . . . . . . . . . . . 23

1.4 An automaton of four states. The corresponding subset transition

graph is shown in figure 1.5. . . . . . . . . . . . . . . . . . . . . . . . 27

1.5 The subset transition graph of the automaton featured in figure 1.4. . 28

1.6 Cern´y"sn-state automatonCn. The letterbmaps each state back to itself, with the exception of thenthstate, wherebmapsnto the first state. The letteramaps theithstate to the (i+ 1)thstate (modulo

2.1 The semigroup generated by the elementa. . . . . . . . . . . . . . . 51

3.1 An example of a graph of states, resulting from Eppstein"s pre-processing

technique, without cropping . . . . . . . . . . . . . . . . . . . . . . . 70

3.2 A revised version of figure 3.1, with omission of redundant edges, to

ensure a forest structure . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.3 A skeleton automaton ofmcolumns andp+ 1 rows, derived from a

generic propositional formula ofmclauses overppropositional vari- ables. Each of themcolumns represents a different clause; each of the firstprows represents a propositional variable; the last (ie the (p+1)th) row has a different purpose. An additional "sink state" sits to the side. 87 5

3.4 Eppstein"s automaton constructed for his proof of theNP-completeness

of the problem SYNC. States are linked by each of the input letters a,bto the one below, and finally to the sink state from the last row. Exceptions to this rule indicate the form of thempropositional clauses represented. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

5.1 Illustration of the form of a state transition graph in an automaton

withdirectional input, under the lettera. . . . . . . . . . . . . . . . . 103

5.2 The same state transition graph featured in figure 5.1, underthe letterb.103

5.3 The same state transition graph featured in figure 5.1, underthe letterc.104

6

The University of Manchester

Peter John Walker

Master of Science

quotesdbs_dbs3.pdfusesText_6