International Journal of Foundations of Computer Science

This work investigates an online two stage k-search problem where an online player makes selections in two stages. In the first stage a number of more than k quoted prices are selected as candidates, and then exactly k highest quoted prices are chosen from the candidates in the second stage. The objective is to maximize the total profit of the k final accepted prices. We mainly propose a deterministic online algorithm and prove that it is optimal in competitiveness. A further discussion is given considering various relationships between the value of k and the number of candidates.

In distributed storage systems, codes with lower repair locality for each coordinate are much more desirable since they can reduce the disk I/O complexity for repairing a failed node. The ith coordinate of a linear code 𝒞 is said to have $(r_i,{\delta }_i)$ locality if there exist δ_i non-overlapping local repair sets of size no more than r_i, where a local repair set of one coordinate is defined as the set of some other coordinates by which one can recover the value at this coordinate. In this paper, we consider linear codes with information $(r_{\min },{\delta }_{\min };r_{\max },{\delta }_{\max })$ locality, where there exists an information set I such that for each $i\in I$, the ith coordinate has $(r_i,{\delta }_i)$ locality and $\min \{r_i:i\in I\}=r_{\min ,}\max \{r_i:i\in I\}=r_{\max ,}\min \{{\delta }_i:i\in I\}={\delta }_{\min }$ and $max\{{\delta }_i:i\in I\}={\delta }_{\max }$. We derive a lower bound on the codeword length n for any linear [n, k, d] code with information $(r_{\min },{\delta }_{\min };r_{\max },{\delta }_{\max })$ locality. Particularly, we indicate that some existing bounds can be deduced from our result by restrictions on parameters.

We study the state complexity of catenation combined with symmetric difference. First, an upper bound is computed using some combinatoric tools. Then, this bound is shown to be tight by giving a witness for it. Moreover, we relate this work with the study of state complexity for two other combinations: catenation with union and catenation with intersection. We extract a unified approach which allows to obtain the state complexity of any combination involving catenation and a binary boolean operation.

We introduce subtree-free regular tree languages that are closely related to XML schemas and investigate the state complexity of basic operations on subtree-free regular tree languages. The state complexity of an operation for regular tree languages is the number of states that are sufficient and necessary in the worst-case for the minimal deterministic ranked tree automaton that accepts the tree language obtained from the operation. We establish the precise state complexity of (sequential, parallel) concatenation, (bottom-up, top-down) star, intersection and union for subtree-free regular tree languages.

The rupture degree of a graph is a measure of the vulnerability of a graph. In this paper we investigate a refinement that involves the weak version of the parameter. The weak-rupture degree of a connected graph G is defined to be $R_{\omega }\left(G\right)=\max \left\{\omega \left(G-S\right)-\left|S\right|-m_e\left(G-S\right):S\subseteq V\left(G\right),\omega \left(G-S\right)>1\right\}$ where $\omega \left(G-S\right)$ is the number of the components of $\left(G-S\right)$ and $m_e\left(G-S\right)$ is the number of edges of the largest component of $G-S$. Like the rupture degree itself, this is a measure of the vulnerability of a graph, but it is more sensitive. This paper, the weak-rupture degree of some special graphs are obtained and some bounds of the weak-rupture degree are given. Moreover some results about the weak-rupture degree of graphs obtained by graph operations are given.

The vulnerability shows the endurance of the network until the communication collapse after the breakdown of certain stations or communication links. If a spy or a station is invaded in a spy network, then the adjacent stations are treacherous. A vulnerability parameter the neighbor rupture degree can be used to obtain the vulnerability of a spy network. The neighbor rupture degree of a noncomplete connected graph G is defined to be

The characterization of M-equivalence for the Parikh matrices is a decade old open problem. This paper studies Parikh matrices and M-equivalence in relation to the s-shuffle operator for the binary alphabet. We also study the distance between images under the s-shuffle operator in a graph associated to the corresponding class of M-equivalent words.

This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of invariants presents some symmetric property. We extend this result to a few other sequences.