International Journal of Foundations of Computer Science

We consider ordered multi-pushdown automata, a multi-stack extension of pushdown automata that comes with a constraint on stack operations: a pop can only be performed on the first non-empty stack (which implies that we assume a linear ordering on the collection of stacks). We show that the emptiness problem for multi-pushdown automata is 2ETIME-complete. Containment in 2ETIME is shown by translating an automaton into a grammar for which we can check if the generated language is empty. The lower bound is established by simulating the behavior of an alternating Turing machine working in exponential space. We also compare ordered multi-pushdown automata with the model of bounded-phase (visibly) multi-stack pushdown automata, which do not impose an ordering on stacks, but restrict the number of alternations of pop operations on different stacks.

This paper studies the combination problem of parallel machine scheduling and the vertex cover problem. Wang and Cui developed a $(3-\frac{2}{m+1})$-approximation algorithm for this problem [13], where $m$ is the number of parallel machines. We reduce the approximation factors from $2.33$ to $2.25$ for $m=2$, from $2.5$ to $2.33$ for $m=3$, and to $3-\frac{3}{m+1}$ for $m\ge 4$.

The edge rupture degree of a graph $G$, as one of measurement parameter of network vulnerability, is defined as $Er(G)=max\{\omega (G-S)-|S|-m(G-S):S\subseteq E(G),\omega (G-S)>1\}$, where $\omega (G-S)$ is the number of components of $G-S$ and $m(G-S)$ is the order of a largest component of $G-S$. In this paper, general results on the edge-rupture degree of a graph are considered. Firstly, some bounds on edge rupture degree are given. Further, edge rupture degree of some graphs is caculated. Also some results are given about this parameter with others. Finally, we discuss edge rupture degree of the complement graph and give the Nordhaus–Gaddum-type results for edge rupture degree.

Quantitative models may exhibit sophisticated behaviour that includes having multiple steady states, bistability, limit cycles, and period-doubling bifurcation. Such behaviour is typically driven by the numerical dynamics of the model, where the values of various numerical parameters play the crucial role. We introduce in this paper natural correspondents of these concepts to reaction systems modelling, a framework based on elementary set theoretical, forbidding/enforcing-based mechanisms. We construct several reaction systems models exhibiting these properties.

In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location problems, and biotechnology, among others. We assume that the value of each vertex identifier can take any value of length $O(logn)$ bits. The execution time of this algorithm is $O(n)$ rounds or $O(n^2)$ time steps. Our algorithm matches the state of the art results for this problem, following an entirely different approach. Our approach allows the computation of the maximum 2-packing when the cactus is a ring.

A $k$-container $C(u,v)$ of a graph $G$ is a set of $k$ internally disjoint paths between $u$ and $v$. A $k$-container $C(u,v)$ of $G$ is a $k^{\ast }$-container if it is a spanning subgraph of $G$. A graph $G$ is $k^{\ast }$-connected if there exists a $k^{\ast }$-container between any two different vertices of G. A $k$-regular graph $G$ is super spanning connected if $G$ is $i^{\ast }$-container for all $1\le i\le k$. In this paper, we prove that the arrangement graph $A_{n,k}$ is super spanning connected if $n\ge 4$ and $n-k\ge 2$.