International Journal of Foundations of Computer Science

We complete the initial study of jumping finite automata, which was started in a former article of Meduna and Zemek [7]. The open questions about basic closure properties are solved. Besides this, we correct erroneous results presented in the article. Finally, we point out important relations between jumping finite automata and some other models studied in the literature.

The satisfiability problem of the branching time logic CTL is studied in terms of computational complexity. Tight upper and lower bounds are provided for each temporal operator fragment. In parallel, the minimal model size is studied with a suitable notion of minimality. Thirdly, flat CTL is investigated, i.e., formulas with very low temporal operator nesting depth. A sharp dichotomy is shown in terms of complexity and minimal models: Temporal depth one has low expressive power, while temporal depth two is equivalent to full CTL.

More and more parallel computing platforms are built upon hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like General Purpose Graphics Processing Units (GPGPUs). We present in this paper a new method for scheduling efficiently parallel applications with $m$ CPUs and $k$ GPGPUs, where each task of the application can be processed either on an usual core (CPU) or on a GPGPU. We consider the problem of scheduling $n$ independent tasks with the objective to minimize the time for completing the whole application (makespan). This problem is NP-hard, thus, we present two families of approximation algorithms that can achieve approximation ratios of $\frac{2q+1}{2q}+𝜖$ or $\frac{2(q+1)}{2q+1}+𝜖$ for any integer $q\ge 1$ when only one GPGPU is considered, and $\frac{2q+1}{2q}+\frac{1}{2qk}+𝜖$ or $\frac{2(q+1)}{2q+1}+\frac{1}{(2q+1)k}+𝜖$ for $k\ge 2$ GPGPUs, where $𝜖$ is an arbitrary small value which corresponds to the target accuracy of a binary search. The proposed method is based on a dual approximation scheme that uses a dynamic programming algorithm. The associated computational costs are for the first (resp. second) family in ${𝒪}(n^2{k}^{q+1}{m}^q)$ (resp. ${𝒪}(n^2{k}^{q+2}{m}^{q+1})$) per step of dual approximation. The greater the value of parameter $q$, the better the approximation, but the more expensive the computational cost. Finally, we propose a relaxed version of the algorithm which achieves a running time in ${𝒪}(nlogn)$ with a constant approximation bound of $2$. This last result is compared to the state-of-the-art algorithm HEFT. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes.

Two edges $e_1$ and $e_2$ in a graph $G$ are said to be adjacent if they have a vertex in common, and distance two apart if they are nonadjacent but both are adjacent to a common edge. An $L(2,1)$-edge-labeling of a graph $G$ is an assignment of nonnegative integers, called labels, to the edges of $G$ such that the difference between labels of any two adjacent edges is at least $2$, and the labels of any two edges that are distance two apart are different. The span of an $L(2,1)$-edge-labeling of a graph $G$ is the difference between the maximum and minimum labels. The minimum span over all $L(2,1)$-edge-labelings of a graph $G$ is called the $L(2,1)$-edge-labeling number of $G$, denoted by ${\lambda }^{\prime }(G)$. For $k\ge 3$, the edge-path-replacement of a graph $G$, denoted by $G(P_k)$, is a graph obtained by replacing each edge of $G$ with a path $P_k$ on $k$ vertices. This paper investigates the $L(2,1)$-edge-labeling number of the edge-path-replacement $G(P_k)$ of a graph $G$ for $k\ge 3$. We get the following main results: $(1)$ Let $G$ be a graph with maximum degree $\mathrm{\Delta }\ge 4$ and $k$ be an integer not less than $4$, then $2\mathrm{\Delta }-2\le {\lambda }^{\prime }(G(P_4))\le 2\mathrm{\Delta }$ if $\mathrm{\Delta }$ is odd, and otherwise ${\lambda }^{\prime }(G(P_k))=2\mathrm{\Delta }-2$. $(2)$ Let $G$ be a graph with maximum degree $\mathrm{\Delta }$. Then $2\mathrm{\Delta }-2\le {\lambda }^{\prime }(G(P_3))\le 3\mathrm{\Delta }-2$ when $\mathrm{\Delta }$ is even, and $2\mathrm{\Delta }-2\le {\lambda }^{\prime }(G(P_3))\le 3\mathrm{\Delta }+1$ when $\mathrm{\Delta }$ is odd.

In earlier versions of the community discovering problem, the overlap between communities was restricted by a simple count upper-bound. In this paper, we introduce the $\mathrm{\Pi }$-Packing with $\alpha ()$-Overlap problem to allow for more complex constraints in the overlap region than those previously studied. Let ${{𝒱}}^r$ be all possible subsets of vertices of $V(G)$ each of size at most $r$, and $\alpha :{{𝒱}}^r\times {{𝒱}}^r\to \{0,1\}$ be a function. The $\mathrm{\Pi }$-Packing with $\alpha ()$-Overlap problem seeks at least $k$ induced subgraphs in a graph $G$ subject to: (i) each subgraph has at most $r$ vertices and obeys a property $\mathrm{\Pi }$, and (ii) for any pair $H_i,H_j$, with $i\ne j$, $\alpha (H_i,H_j)=0$ (i.e., the pair $H_i,H_j$ does not conflict). We also consider a variant that arises in clustering applications: each subgraph of a solution must contain a set of vertices from a given collection of sets ${𝒞}$, and no pair of subgraphs may share vertices from the sets of ${𝒞}$. In addition, we propose similar formulations for packing hypergraphs. We give an $O(r^{rk}{k}^{(r+1)k}{n}^r)$ algorithm for our problems where $k$ is the parameter and $c$ and $r$ are constants, provided that: (i) $\mathrm{\Pi }$ is computable in polynomial time in $n$ and (ii) the function $\alpha ()$ satisfies specific conditions. Specifically, $\alpha ()$ is hereditary, applicable only to overlapping subgraphs, and computable in polynomial time in $n$ and $r$. Motivated by practical applications we give several examples of $\alpha ()$ functions which meet those conditions.

The notion of strong $M$-equivalence was introduced as an order-independent alternative to $M$-equivalence for Parikh matrices. This paper further studies the notions of $M$-equivalence and strong $M$-equivalence. Certain structural properties of $M$-equivalent ternary words are presented and then employed to (partially) characterize pairs of ternary words that are ME-equivalent (i.e. obtainable from one another by certain elementary transformations). Finally, a sound rewriting system in determining strong $M$-equivalence is obtained for the ternary alphabet.