Efficient broadcasting in radio networks with long-range interference

We study broadcasting, also known as one-to-all communication, in synchronous radio networks with known topology modeled by undirected (symmetric) graphs, where the interference range of a node is likely exceeding its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge they cannot communicate directly and transmission of one node disables recipience of any message at the other node. For a network $G,$ we term the smallest integer $d$ , s.t., for any interference edge $e$ there exists a simple path formed of at most $d$ transmission edges connecting the endpoints of $e$ as its interference distance $d_I$ . In this model the schedule of transmissions is precomputed in advance. It is based on the full knowledge of the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on a bounded number of transmissions executed at each node. We adopt $n$ as the number of nodes, $D_T$ is the diameter of the subnetwork induced by the transmission edges, and $\varDelta $ refers to the maximum combined degree (formed of transmission and interference edges) of the network. We contribute the following new results: (1) We prove that for networks with the interference distance $d_I\ge 2$ any broadcasting schedule requires at least $D_T+\varOmega (\varDelta \cdot \frac{\log {n}}{\log {\varDelta }})$ rounds. (2) We provide for networks modeled by bipartite graphs an algorithm that computes $1$ -shot (each node transmits at most once) broadcasting schedules of length $O(\varDelta \cdot \log {n})$ . (3) The main result of the paper is an algorithm that computes a $1$ -shot broadcasting schedule of length at most $4 \cdot D_T + O(\varDelta \cdot d_I \cdot \log ^4{n})$ for networks with arbitrary topology. Note that in view of the lower bound from (1) if $d_I$ is poly-logarithmic in $n$ this broadcast schedule is a poly-logarithmic factor away from the optimal solution.     

The categories L-\mathbf{Top}_{0} and L-\mathbf{Sob} as epireflective hulls

We show that the category \(L\) - \(\mathbf{Top}_{0}\) of \(T_{0}\) - \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}\) of \(L\) -topological spaces and the category \(L\) - \(\mathbf{Sob}\) of sober \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}_{0}\) .     

Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

Some kinds of primitive and non-primitive words

If the length of a primitive word \(p\) is equal to the length of another primitive word \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . This was obtained separately by Tetsuo Moriya in 2008 and Shyr and Yu in 1994. In this paper, we prove that if the length of \(p\) is divisible by the length of \(q\) and the length of \(p\) is less than or equal to \(m\) times the length of \(q\) , then \(p^{n}q^{m}\) is a primitive word for any \(n,m\ge 1\) and \((n,m)\ne (1,1)\) . Then we show that if \(uv,u\) are non-primitive words and the length of \(u\) is divisible by the length \(v\) or one of the length of \(u\) and \(uv\) is odd for any two nonempty words \(u\) and \(v\) , then \(u\) is a power of \(v\) .     

Locality and checkability in wait-free computing

This paper studies notions of locality that are inherent to the specification of distributed tasks by identifying fundamental relationships between the various scales of computation, from the individual process to the whole system. A locality property called projection-closed is identified. This property completely characterizes tasks that are wait-free checkable, where a task $T =(\mathcal{I },\mathcal{O },\varDelta )$ T = ( I , O , Δ ) is said to be checkable if there exists a distributed algorithm that, given $s\in \mathcal{I }$ s ∈ I and $t\in \mathcal{O }$ t ∈ O , determines whether $t\in \varDelta {(s)}$ t ∈ Δ ( s ) , i.e., whether $t$ t is a valid output for $s$ s according to the specification of $T$ T . Projection-closed tasks are proved to form a rich class of tasks. In particular, determining whether a projection-closed task is wait-free solvable is shown to be undecidable. A stronger notion of locality is identified by considering tasks whose outputs “look identical” to the inputs at every process: a task $T= (\mathcal{I },\mathcal{O },\varDelta )$ T = ( I , O , Δ ) is said to be locality-preserving if $\mathcal{O }$ O is a covering complex of $\mathcal{I }$ I . We show that this topological property yields obstacles for wait-free solvability different in nature from the classical impossibility results. On the other hand, locality-preserving tasks are projection-closed, and thus they are wait-free checkable. A classification of locality-preserving tasks in term of their relative computational power is provided. This is achieved by defining a correspondence between subgroups of the edgepath group of an input complex and locality-preserving tasks. This correspondence enables to demonstrate the existence of hierarchies of locality-preserving tasks, each one containing, at the top, the universal task (induced by the universal covering complex), and, at the bottom, the trivial identity task.     

Characterization of extended filters in residuated lattices

We give a characterization theorem of extended filters on residuated lattices, from which many results are immediately obtained. We show that, for a bounded integral commutative residuated lattice X, (1) an extended filter $E_F (B)$ associated with $B$ is characterized by $E_F (B) = [B) \rightarrow F$ , where $B\subseteq X$ and $F$ is a filter of $X$ ; (2) the class $E(B)$ of all extended filters associated with $B$ is a complete Heyting algebra. (3) the class $S(B)$ of all stable filters relative to $B\subseteq X$ is also a complete Heyting algebra.     

Isomorphisms and functors of fuzzy sets and cut systems

Any fuzzy set \(X\) in a classical set \(A\) with values in a complete (residuated) lattice \( Q\) can be identified with a system of \(\alpha \) -cuts \(X_{\alpha }\) , \(\alpha \in Q\) . Analogical results were proved for sets with similarity relations with values in \( Q\) (e.g. \( Q\) -sets), which are objects of two special categories \({\mathbf K}={Set}( Q)\) or \({SetR}( Q)\) of \( Q\) -sets, and for fuzzy sets defined as morphisms from an \( Q\) -set into a special \(Q\) -set \(( Q,\leftrightarrow )\) . These fuzzy sets can be defined equivalently as special cut systems \((C_{\alpha })_{\alpha }\) , called f-cuts. This equivalence then represents a natural isomorphism between covariant functor of fuzzy sets \(\mathcal{F}_{\mathbf K}\) and covariant functor of f-cuts \(\mathcal{C}_{\mathbf K}\) . In this paper, we prove that analogical natural isomorphism exists also between contravariant versions of these functors. We are also interested in relationships between sets of fuzzy sets and sets of f-cuts in an \(Q\) -set \((A,\delta )\) in the corresponding categories \({Set}( Q)\) and \({SetR}( Q)\) , which are endowed with binary operations extended either from binary operations in the lattice \(Q\) , or from binary operations defined in a set \(A\) by the generalized Zadeh’s extension principle. We prove that the resulting binary structures are (under some conditions) isomorphic.     

Reduced ordered binary decision diagram with implied literals: a new knowledge compilation approach

Reduced ordered binary decision diagram (ROBDD) is one of the most influential knowledge compilation languages. We generalize it by associating some implied literals with each node to propose a new language called ROBDD with implied literals (ROBDD- $L$ ) and show that ROBDD- $L$ can meet most of the querying requirements involved in the knowledge compilation map. Then, we discuss a kind of subsets of ROBDD- $L$ called ROBDD- $L_i$ with precisely $i$ implied literals $(0\le i\le \infty )$ , where ROBDD- $L_0$ is isomorphic to ROBDD. ROBDD- $L_i$ has uniqueness over any given linear order of variables. We mainly focus on ROBDD- $L_\infty $ and demonstrate that: (a) it is a canonical representation on any given variable order; (b) it is the most succinct subset in ROBDD- $L$ and thus also meets most of the querying requirements; (c) given any logical operation ROBDD supports in polytime, ROBDD- $L_\infty $ can also support it in time polynomial in the sizes of the equivalent ROBDDs. Moreover, we propose an ROBDD- $L_i$ compilation algorithm for any $i$ and an ROBDD- $L_\infty $ compilation algorithm, and then we implement an ROBDD- $L$ package called BDDjLu. Our preliminary experimental results indicate that: (a) the compilation results of ROBDD- $L_\infty $ are significantly smaller than those of ROBDD; (b) the standard d-DNNF compiler c2d and our ROBDD- $L_\infty $ compiler do not dominate the other, yet ROBDD- $L_\infty $ has canonicity and supports more querying requirements and relatively efficient logical operations; and (c) the method that first compiles knowledge base into ROBDD- $L_\infty $ and then converts ROBDD- $L_\infty $ into ROBDD provides an efficient ROBDD compiler.     

Informational correlation between two parties of a quantum system: spin-1/2 chains

We introduce the informational correlation \(E^{AB}\) between two interacting quantum subsystems \(A\) and \(B\) of a quantum system as the number of arbitrary parameters \(\varphi _i\) of a unitary transformation \(U^A\) (locally performed on the subsystem \(A\) ) which may be detected in the subsystem \(B\) by the local measurements. This quantity indicates whether the state of the subsystem \(B\) may be effected by means of the unitary transformation applied to the subsystem \(A\) . Emphasize that \(E^{AB}\ne E^{BA}\) in general. The informational correlations in systems with tensor product initial states are studied in more details. In particular, it is shown that the informational correlation may be changed by the local unitary transformations of the subsystem \(B\) . However, there is some non-reducible part of \(E^{AB}(t)\) which may not be decreased by any unitary transformation of the subsystem \(B\) at a fixed time instant \(t\) . Two examples of the informational correlations between two parties of the four-node spin-1/2 chain with mixed initial states are studied. The long chains with a single initially excited spin (the pure initial state) are considered as well.     

Completions of cut systems in Q-sets

Let $ Q$ be a complete residuated lattice. Let $\text {SetR}(Q)$ be the category of sets with similarity relations with values in $ Q$ (called $ Q$ -sets), which is an analogy of the category of classical sets with relations as morphisms. A cut in an $ Q$ -set $(A,\delta )$ is a system $(C_{\alpha })_{\alpha \in Q}$ , where $C_{\alpha }$ are subsets of $A\times Q$ . It is well known that in the category $\text {SetR}(Q)$ , there is a close relation between special cuts (called f-cuts) in an $ Q$ -set on one hand and fuzzy sets in the same $ Q$ -set, on the other hand. Moreover, there exists a completion procedure according to which any cut $(C_{\alpha })_{\alpha }$ can be extended onto an f-cut $(\overline{C_{\alpha }})_{\alpha }$ . In the paper, we prove that the completion procedure is, in some sense, the best possible. This will be expressed by the theorem which states that the category of f-cuts is a full reflective subcategory in the category of cuts.     

Finding large k-clubs in undirected graphs

Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, $k$ -clique, and $k$ -clan. The concept of $k$ -club is one of them. A $k$ -club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter $k$ . It is a relaxation of a clique, which induces a subgraph of diameter $1$ . We conducted algorithmic studies on finding a $k$ -club of size as large as possible. In this paper, we show that one can find a $k$ -club of maximum size in $O^{*}(1.62^n)$ time where $n$ is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a $k$ -club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called $k$ -DN which, under deletion of vertices from a graph, maintains for a given vertex $v$ the set of vertices at distances at most $k$ . From the experimental results that we obtained, we concluded that a $k$ -club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, $k$ -clubs of maximum size in most of experimental instances. The gap between the size of a $k$ -club of maximum size and a $k$ -club found by IDROP is a constant for the number of vertices that we are able to test.     

Fault tolerance of hypercubes and folded hypercubes

Let \(G = (V,E)\) be a connected graph. The conditional edge connectivity \(\lambda _\delta ^k(G)\) is the cardinality of the minimum edge cuts, if any, whose deletion disconnects \(G\) and each component of \(G - F\) has \(\delta \ge k\) . We assume that \(F \subseteq E\) is an edge set, \(F\) is called edge extra-cut, if \(G - F\) is not connected and each component of \(G - F\) has more than \(k\) vertices. The edge extraconnectivity \(\lambda _\mathrm{e}^k(G)\) is the cardinality of the minimum edge extra-cuts. In this paper, we study the conditional edge connectivity and edge extraconnectivity of hypercubes and folded hypercubes.     

A note on the factorization conjecture

We give partial results on the factorization conjecture on codes proposed by Schützenberger. We consider a family of finite maximal codes $C$ over the alphabet $A = \{a, b\}$ and we prove that the factorization conjecture holds for these codes. This family contains $(p,4)$ -codes, where a $(p,4)$ -code $C$ is a finite maximal code over $A$ such that each word in $C$ has at most four occurrences of $b$ and $a^p \in C$ , for a prime number $p$ . We also discuss the structure of these codes. The obtained results once again show relations between factorizations of finite maximal codes and factorizations of finite cyclic groups.     

Approximation of integrable functions based on \phi -transform

Let \(E\) be a bounded subset of real line which contains its infimum and supremum. In this paper, we have defined the \(\phi -\) transform and its inverse, where \(\phi \) is a function from \(E\) into \((0,1]\) . We will have shown that real-valued integrable functions on \([a, b]\) and real-valued continuous functions on \(E\) can be approximated by this transformation with an arbitrary precision.     

A sparse {\varvec{L}}_{2}-regularized support vector machines for efficient natural language learning

Linear kernel support vector machines (SVMs) using either $L_{1}$ -norm or $L_{2}$ -norm have emerged as an important and wildly used classification algorithm for many applications such as text chunking, part-of-speech tagging, information retrieval, and dependency parsing. $L_{2}$ -norm SVMs usually provide slightly better accuracy than $L_{1}$ -SVMs in most tasks. However, $L_{2}$ -norm SVMs produce too many near-but-nonzero feature weights that are highly time-consuming when computing nonsignificant weights. In this paper, we present a cutting-weight algorithm to guide the optimization process of the $L_{2}$ -SVMs toward a sparse solution. Before checking the optimality, our method automatically discards a set of near-but-nonzero feature weight. The final objects can then be achieved when the objective function is met by the remaining features and hypothesis. One characteristic of our cutting-weight algorithm is that it requires no changes in the original learning objects. To verify this concept, we conduct the experiments using three well-known benchmarks, i.e., CoNLL-2000 text chunking, SIGHAN-3 Chinese word segmentation, and Chinese word dependency parsing. Our method achieves 1–10 times feature parameter reduction rates in comparison with the original $L_{2}$ -SVMs, slightly better accuracy with a lower training time cost. In terms of run-time efficiency, our method is reasonably faster than the original $L_{2}$ -regularized SVMs. For example, our sparse $L_{2}$ -SVMs is 2.55 times faster than the original $L_{2}$ -SVMs with the same accuracy.     

Simple characterization of strict residuated lattices with an involutive negation

We consider property of strict residuated lattices (SRL-algebras) with a new involutive negation $\lnot, $ called here by SRL $_{\lnot }$ -algebras, and give a simple characterization of SRL $_{\lnot }$ -algebras. We also prove a prime filter theorem of SRL $_{\lnot }$ -algebras, from which we conclude that every linearly ordered SRL $_{\lnot }$ -algebra is simple. As a corollary to this fact, we have a well-known result that every SML $_{\lnot }$ -algebra (SBL $_{\lnot }$ -algebra) is a subdirect product of linearly ordered SML $_{\lnot }$ -algebras (SBL $_{\lnot }$ -algebras).     

Solving Convection-Diffusion Problems on Curved Domains by Extensions from Subdomains

We present a technique for numerically solving convection-diffusion problems in domains $\varOmega $ with curved boundary. The technique consists in approximating the domain $\varOmega $ by polyhedral subdomains $\mathsf{{D}}_h$ where a finite element method is used to solve for the approximate solution. The approximation is then suitably extended to the remaining part of the domain $\varOmega $ . This approach allows for the use of only polyhedral elements; there is no need of fitting the boundary in order to obtain an accurate approximation of the solution. To achieve this, the boundary condition on the border of $\varOmega $ is transferred to the border of $\mathsf{D }_h$ by using simple line integrals. We apply this technique to the hybridizable discontinuous Galerkin method and provide extensive numerical experiments showing that, whenever the distance of $\mathsf{{D}}_h$ to $\partial \varOmega $ is of order of the meshsize $h$ , the convergence properties of the resulting method are the same as those for the case in which $\varOmega =\mathsf{{D}}_h$ . We also show numerical evidence indicating that the ratio of the $L^2(\varOmega )$ norm of the error in the scalar variable computed with $d>0$ to that of that computed with $d=0$ remains constant (and fairly close to one), whenever the distance $d$ is proportional to $\min \{h,Pe^{-1}\}/(k+1)^2$ , where $Pe$ is the so-called Péclet number.     

Strong Conflict-Free Coloring for Intervals

We consider the \(k\) -strong conflict-free ( \(k\) -SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval \(I\) of the family there are at least \(k\) colors each appearing exactly once in \(I\) . We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when \(k=1\) and \(5-\frac{2}{k}\) when \(k\ge 2\) . In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any \(k \ge 1\) . We also provide, in case \(k=O({{\mathrm{polylog}}}(n))\) , a quasipolynomial time algorithm to decide the existence of a \(k\) -SCF coloring that uses at most \(q\) colors.     

Growth rates for persistently excited linear systems

We consider a family of linear control systems \(\dot{x}=Ax+\alpha Bu\) on \(\mathbb {R}^d\) , where \(\alpha \) belongs to a given class of persistently exciting signals. We seek maximal \(\alpha \) -uniform stabilization and destabilization by means of linear feedbacks \(u=Kx\) . We extend previous results obtained for bidimensional single-input linear control systems to the general case as follows: if there exists at least one \(K\) such that the Lie algebra generated by \(A\) and \(BK\) is equal to the set of all \(d\times d\) matrices, then the maximal rate of convergence of \((A,B)\) is equal to the maximal rate of divergence of \((-A,-B)\) . We also provide more precise results in the general single-input case, where the above result is obtained under the simpler assumption of controllability of the pair \((A,B)\) .     

Distinguishing and relating higher-order and first-order processes by expressiveness

This is a paper on distinguishing and relating two important kinds of calculi through expressiveness, settling some critical but long unanswered questions. The delimitation of higher-order and first-order process calculi is a basic and pivotal topic in the study of process theory. Particularly, expressiveness studies mutual encodability, which helps decide whether process-passing or name-passing is more fundamental, and the way they ought to be used in both theory and practice. In this paper, we contribute to such demarcation with three major results. Firstly $\pi $ (first-order pi-calculus) can faithfully express $\varPi $ (basic higher-order pi-calculus). The calculus $\varPi $ has the elementary operators (input, output, composition and restriction). This actually is a corollary of a more general result, that $\pi $ can encode $\varPi ^r$ ( $\varPi $ enriched with the relabelling operator). Secondly $\varPi $ cannot interpret $\pi $ reasonably. This is of more significance since it separates $\varPi $ and $\pi $ by drawing a well-defined boundary. Thirdly an encoding from $\pi $ to $\varPi ^r$ is revisited and discussed, which not only implies how to make $\varPi $ more useful but also stresses the importance of name-passing in $\pi $ .