Catálogo de publicaciones - libros

A word is called synchronizing (recurrent, reset, directable) word of deterministic finite automaton (DFA) if brings all states of the automaton to an unique state. Černy conjectured in 1964 that every -state synchronizable automaton possesses a synchronizing word of length at most ( − 1). The problem is still open.

It will be proved that the minimal length of synchronizing word is not greater than ( − 1)/2 for every -state ( > 2) synchronizable DFA with transition monoid having only trivial subgroups (such automata are called ). This important class of DFA accepting precisely star-free languages was involved and studied by Schŭtzenberger. So for aperiodic automata as well as for automata accepting only star-free languages, the Černý conjecture holds true.

Some properties of an arbitrary synchronizable DFA and its transition semigroup were established.

In this paper we explore the biclique structure of a biconvex bipartite graph . We define two concatenation operators on bicliques of . According to these operations, we show that can be decomposed into two chain graphs and , and a bipartite permutation graph . Using this representation, we propose linear-time algorithms for the treewidth and pathwidth problems on biconvex bipartite graphs.

The problem is to decide whether there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given is termed .

We show that fixed-vertex subgraph homeomorphism for a pattern graph on vertices and a host graph on vertices can be solved in time (2) or in time (3) and polynomial space. In effect, we obtain new non-trivial upper time-bounds on the exact complexity of the problem of finding vertex-disjoint paths and general subgraph homeomorphism.

We study the problem of searching for a mobile intruder in a polygonal region by two guards. The objective is to decide whether there exists a for two guards to detect the intruder, no matter how fast he moves, and if so, generate a search schedule. During the search, two guards are required to walk on the boundary of continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards, and give an optimal () time algorithm for determining the two-guard searchability of a polygon and an algorithm for generating a search schedule in time linear in its size.

Given a complete graph  = (,)with a cost function : →ℝ and a vertex subset  ⊂ , an is a Steiner tree which contains all vertices in such that each vertex in is restricted to be an internal vertex. The is to find an internal Steiner tree whose total costs ∑ (,) is minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present an approximation algorithm with approximation ratio 2 + 1 for the problem, where is the best known approximation ratio for the Steiner tree problem.

We investigate the group key management problem for broadcasting applications. Previous work showed that, in handling key updates, batch rekeying can be more cost-effective than individual rekeying. One model for batch rekeying is to assume that every user has probability of being replaced by a new user during a batch period with the total number of users unchanged. Under this model, it was recently shown that an optimal key tree can be constructed in linear time when is a constant and in () time when →0. In this paper, we investigate more efficient algorithms for the case →0, i.e., when membership changes are sparse. We design an () heuristic algorithm for the sparse case and show that it produces a nearly 2-approximation to the optimal key tree. Simulation results show that its performance is even better in practice. We further design a refined heuristic algorithm and show that it achieves an approximation ratio of 1 +  as →0.

For generalized Reed-Solomon codes, it has been proved [7] that the problem of determining if a received word is a deep hole is co-NP-complete. The reduction relies on the fact that the evaluation set of the code can be exponential in the length of the code – a property that practical codes do not usually possess. In this paper, we first present a much simpler proof of the same result. We then consider the problem for standard Reed-Solomon codes, i.e. the evaluation set consists of all the nonzero elements in the field. We reduce the problem of identifying deep holes to deciding whether an absolutely irreducible hypersurface over a finite field contains a rational point whose coordinates are pairwise distinct and nonzero. By applying Cafure-Matera estimation of rational points on algebraic varieties, we prove that the received vector (())_ ∈  for the Reed-Solomon [ − 1,],  < , cannot be a deep hole, whenever () is a polynomial of degree  +  for 1 ≤  < .

We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result, we show that if the quantum -party communication complexity of a function is , then its classical -party communication is . Finding such an would allow us to prove strong classical lower bounds for  ≥ log players and make progress towards solving a main open question about symmetric circuits.

The computation on algebraic immunity (AI) of symmetric boolean functions includes: determining the AI of a given symmetric function and searching all symmetric functions with  =  or  ≥ , where . In this paper we firstly showed a necessary and sufficient condition of AI of symmetric boolean functions and then proposed several efficient algorithms on computation of algebraic immunity of symmetric boolean functions. By these algorithms we could assess the vulnerability of symmetric boolean functions against algebraic/fast algebraic attacks efficiently, and find all symmetric functions having a given algebraic immunity () = , for some 0 ≤  ≤ .

In previous work we have introduced an average case measure for the time complexity of Boolean circuits – that is the delay between feeding the input bits into a circuit and the moment when the results are ready at the output gates – and analysed this complexity measure for prefix computations. Here we consider the problem to sort large integers that are given in binary notation. Contrary to a where a basic computational element, a comparator, is charged with a single time step to compare two elements, in a ′ a comparison of two binary numbers has to be implemented by a Boolean subcircuit CM called that is built from Boolean gates of bounded fanin. Thus, compared to , the depth of ′ will be larger by a factor up to the depth of CM.

Our goal is to minimize the average delay of bit comparator sorting circuits. The worst-case delay can be estimated by the depth of the circuit. For this worst-case measure two topologically quite different designs seems to be appropriate for the comparator modules: a tree-like one if the inputs are long numbers, otherwise a linear array working in a pipelined fashion. Inserting these into a word comparator circuit we get bit level sorting circuits for binary numbers of length for which the depth is either increased by a multiplicative factor of oder log or by an additive term of order .

We show that this obvious solution can be improved significantly by constructing efficient sorting and merging circuits for the bit model that only suffer a constant factor time loss on the average if the inputs are uniformly distributed. This is done by designing suitable hybrid architectures of tree compaction and pipelining. These results can also be extended to classes of nonuniform distributions if we put a bound on the complexity of the distributions themselves.