International Journal of Foundations of Computer Science

Glushkov automaton is an efficient structure for matching regular expressions. We present an $O(k{2}^k)$ bits space representation of Glushkov automata of regular expressions, where $k$ is the number of strings in the regular expression. The state transition runs in time $O(\lceil m/w\rceil logk)$, where $w$ is the size of machine words, and $m$ is the number of states in the Glushkov automaton. For $k\le 4m/(\sqrt{8w+9}-1)$, the time is $O(\lceil m/w\rceil )$. Our approach is based on two operations on words that retrieve and set bits on a specific set of positions of a word. We present implementations of these operations using bit-parallelism and a permutation network, which are simple and efficient.

Grain is one of the hardware-oriented finalists of the eSTREAM. The cipher has a cascade connection of an LFSR into an NFSR which is denoted by Cascade Model. In this paper, we study the equivalence relations between state diagrams of two functions, and apply them to the Cascade Models, then some results regarding their equivalence relations are obtained.

The vulnerability measure of a graph or a network depends on robustness of the remained graph, after being exposed to any intervention or attack. In this paper, we consider two edge vulnerability parameters that are the edge neighbor rupture degree and the edge scattering number. The values of these parameters of some specific graphs and their graph operations are calculated. Thus, we analyze and compare which parameter is distinctive for the different type of graphs by using tables.

Four circulant codes form a special class of $2$-generator, index $4$, quasi-cyclic codes. Under some conditions on their generator matrix they can be shown to be self-dual. Artin primitive root conjecture shows the existence of an infinite subclass of these codes satisfying a modified Gilbert–Varshamov bound.

Let $G$ be a graph and $S\subseteq V(G)$. We define by $〈S〉$ the subgraph of $G$ induced by $S$. For each vertex $u\in S$ and for each vertex $v\in S\setminus \{u\}$, $d_{(G,S\setminus \{u\})}(u,v)$ is the length of the shortest path in $〈V(G)-((S-\{u\})-\{v\})〉$ between $u$ and $v$ if such a path exists, and $\infty$ otherwise. For a vertex $u\in S$, let ${\omega }_{(G,S\setminus \{u\})}(u)={\sum }_{v\in S\setminus \{u\}}{(\frac{1}{2})}^{d_{(G,S\setminus \{u\})}(u,v)-1}$ where $\left(\right.\frac{1}{2}{\left)\right.}^{\infty }=0$. Jäger and Rautenbach [27] define a set $S$ of vertices to be exponential independent if ${\omega }_{(G,S\setminus \{u\})}(u)<1$ for every vertex $u$ in $S$. The exponential independence number ${\alpha }_e(G)$ of $G$ is the maximum order of an exponential independent set. In this paper, we give a general theorem and we examine exponential independence number of some tree graphs and thorn graph of some graphs.

This paper studies mathematical properties of reaction systems that were introduced by Ehrenfeucht and Rozenberg as computational models inspired by biochemical reaction in the living cells. In particular, we continue the study on the generative power of functions specified by minimal reaction systems under composition initiated by Salomaa. Allowing degenerate reaction systems, functions specified by minimal reaction systems over a quarternary alphabet that are permutations generate the alternating group on the power set of the background set.

To study the data association, a structure called a hierarchy tree is constructed. It is based on the approach to hierarchical data processing, and constituted by different level partitions of a data set. This leads to the definition of the data association, thereby links two hierarchy trees together. The research on the data association focuses on the way to check whether data are associated with other data. The investigation includes the issues: the intuitive and formal methods for constructing hierarchy trees, the technique of making granules hierarchical, the sufficient and necessary condition for measuring the data association, the analysis of basing the closer data association on the closer data identity, the discussion of connecting numerical information with association closeness, etc. Crucially, the hierarchical data processing and numerical information are important characteristics of the research. As an applied example, two hierarchy trees are set up, demonstrating the hierarchical granulation process of two actual data sets. Data associations between the data sets are characterized by the approach developed in this paper, which provides the basis of algorithm design for the actual problem. In particular, since the research is relevant to granules and alterations of granularity, it may offer an avenue of research on granular computing.

Let $\mathrm{\Sigma }$ be an alphabet having at least three symbols. Let $CFL$ denote the family of all context-free languages over $\mathrm{\Sigma }$, $PEG$ denote the family of all parsing expression grammars over $\mathrm{\Sigma }$, and $PEL$ denote the family of all parsing expression languages over $\mathrm{\Sigma }$. Let $K$ satisfy $K\subseteq CFL$ and “$K\cap PEL\ne \varnothing$”, where we use the double-quoted “$K\cap PEL\ne \varnothing$” in the sense that we can effectively find some $G\in PEG$ such that $L(G)\in K\cap PEL$. Then the following problem is shown to be undecidable: Given $G\in PEG$, decide if $L(G)\in K$. In particular, the following basic problem is shown to be undecidable: Given $G\in PEG$, decide if $L(G)\in CFL$.

We consider the directed Steiner network problem, where given a weighted directed graph $G$ and $p$ pairs of vertices $P=\{(s_1,t_1),\dots ,(s_p,t_p)\}$, one has to find the minimum weight subgraph $H$ of $G$ that contains path from $s_i$ to $t_i$ for all $i$. We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one; and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one.

In the past decades, there has been a burst of activity to simplify implementation of complex software systems. The solution framework in software engineering community for this problem is called component-based software design (CBSD), whereas in the modeling and simulation community it is called composability. Composability is a complex feature due to the challenges of creating components, selecting combinations of components, and integrating the selected components.

In this paper, we address the challenge through the analysis of Component Selection (CS), the NP-complete process of selecting a minimal set of components to satisfy a set of objectives. Due to the computational complexity of CS, we consider approximation algorithms that make the component selection process practical. We define three variations of CS and present good approximation algorithms to find near optimal solutions. In spite of our creation of approximable variants of Component Selection, we prove that the general Component Selection problem is inapproximable.