Theoretical Computer Science, Volume 410, Issues 24-25, Pages 2301-2452 (28 May 2009), Formal Languages and Applications: A Collection of Papers in Honor of Sheng Yu

Preface......Page 1
Introduction......Page 8
Preliminaries......Page 9
Parallelism......Page 10
Computing the parallel complexity: The basic algorithm......Page 11
A faster test for the parallel applicability of a set of operations......Page 12
The new algorithm......Page 13
Discussion......Page 14
References......Page 15
Introduction......Page 16
Cyclotomic cyclic difference sets and their sequences......Page 17
The Dillon--Dobbertin construction......Page 18
The Ding--Helleseth--Martinsen constructions......Page 19
Comments on the N equiv 1 18mu(mod4) case......Page 20
A generic construction of binary sequences with out-of-phase autocorrelation values {-1,3}......Page 21
References......Page 22
Introduction and preliminary considerations......Page 23
Notation and basic notions......Page 24
Definitions......Page 25
Topologies from comparing words......Page 26
Topologies related to the prefix-limit process......Page 27
Adherences as limits......Page 28
Extending partial orders......Page 29
Quasi-right topologies......Page 30
Accumulation points and cluster points......Page 31
Adherences related to the topologies τleq......Page 32
The topology on Xω induced by τleq......Page 33
References......Page 34
Introduction......Page 36
Regex machines: Regex automata systems......Page 37
Main result: Intersection with regular languages......Page 40
Consequences and conclusion......Page 43
References......Page 44
Introduction......Page 45
Word type solutions......Page 46
The conjugator......Page 47
Characterization of conjugacy of finite biprefix codes......Page 48
The conjugator of finite biprefix codes......Page 50
References......Page 51
Introduction......Page 52
Prerequisites......Page 54
Three examples......Page 55
Computational completeness of general SN P systems......Page 57
Unbounded SN P systems......Page 60
0-delay unbounded SN P systems and partially blind counter machines......Page 61
Closure properties and decision problems......Page 63
References......Page 64
Introduction......Page 65
Similarity metric and distance metric......Page 66
Relationship between similarity metric and distance metric......Page 68
Normalized similarity metric......Page 70
Normalized distance metric......Page 73
Set similarity and distance......Page 74
Sequence edit distance and similarity......Page 75
References......Page 76
Introduction......Page 77
Upper bound......Page 78
Lower bound......Page 79
State complexity of L3......Page 81
Upper bound......Page 82
Lower bound......Page 84
From cube to square......Page 88
Nondeterministic state complexity......Page 89
Calculations......Page 90
References......Page 91
Introduction......Page 93
Preliminaries......Page 94
Twin-roots and primitive roots......Page 95
The set of symmetric words in the Chomsky hierarchy......Page 96
On the pseudo-commutativity of languages......Page 98
References......Page 100
Introduction......Page 101
Regularity-preserving index sets......Page 102
Lower bound......Page 103
Decimations of context-free languages......Page 107
References......Page 109
Introduction......Page 110
Disjoint 2-interval pattern matching problem......Page 111
The set of endpoints......Page 112
Arc set PQj, 1jell......Page 113
Arc set STj, 2jell......Page 114
Correctness of the construction......Page 115
Arcs from H to Zu......Page 117
Arcs from Zu to T......Page 118
Arcs from T to Vv and from Vu to Vv......Page 119
Arcs from Z'ell to T'......Page 120
Correctness......Page 121
References......Page 123
Introduction......Page 124
Preliminaries......Page 125
Worst case scenario for unary languages......Page 126
Cover automata......Page 128
References......Page 130
Introduction......Page 131
Properties......Page 132
State complexity......Page 134
Unique concatenation......Page 135
Unique star......Page 137
Application: 2-DFAs with a pebble......Page 139
References......Page 140
Introduction......Page 142
Preliminaries......Page 143
A strategy for computing the sizes of minimal elements......Page 144
General Petri nets......Page 145
Parametric clocked Petri nets......Page 148
Subclasses of Petri nets......Page 149
Conclusion......Page 151
References......Page 152