185
click to vote
FCT
2009
Springer
15 years 10 months ago
2009
Springer
We show that the reachability problem for directed graphs that are either K3,3-free or K5-free is in unambiguous log-space, UL coUL. This significantly extends the result of Bour...
171
click to vote
FCT
2009
Springer
15 years 10 months ago
2009
Springer
Given a set P of natural numbers, we consider infinite games where the winning condition is a regular -language parametrized by P. In this context, an -word, representing a play, h...
154
Voted
FCT
2009
Springer
15 years 11 months ago
2009
Springer
156
click to vote
FCT
2009
Springer
15 years 11 months ago
2009
Springer
Abstract. In the frequency allocation problem we are given a cellular telephone network whose geographical coverage area is divided into cells where phone calls are serviced by fre...
169
Voted
FCT
2009
Springer
15 years 11 months ago
2009
Springer
Abstract. We present an algorithm for asymptotically efficient multiway blockwise in-place merging. Given an array A containing sorted subsequences A1, . . . , Ak of respective le...
179
Voted
FCT
2009
Springer
16 years 28 days ago
2009
Springer
We argue that closure operators are fundamental tools for the study of relationships between order structures and their sequence representations. We also propose and analyse a clos...
188
Voted
FCT
2009
Springer
16 years 28 days ago
2009
Springer
We give small universal Turing machines with state-symbol pairs of (6, 2), (3, 3) and (2, 4). These machines are weakly universal, which means that they have an infinitely repeate...
151
Voted
FCT
2009
Springer
16 years 28 days ago
2009
Springer
