The notion of a quasi-order generated by a homomorphism from the semigroup of all words onto a finite ordered semigroup was introduced by Bucher et al. (Theor. Comput. Sci. 40, 131–148 1985). It naturally occurred in their studies of derivation …

A pumping lemma for a class of languages $$\varvec{\mathcal {C}}$$ C is often used to show particular languages are not in $$\varvec{\mathcal {C}}$$ C . In contrast, we show that a pumping lemma for a class of languages $$\varvec{\mathcal {C}}$$ C …

In the well known planted clique problem, a clique (or alternatively, an independent set) of size k is planted at random in an Erdos-Renyi random G(n, p) graph, and the goal is to design an algorithm that finds the maximum clique (or independent …

We consider a setting with agents that have preferences over alternatives and are partitioned into disjoint districts. The goal is to choose one alternative as the winner using a mechanism which first decides a representative alternative for each …

We study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph describing habitats or routes of wildlife animals and possibilities of …

Many Boolean functions that need to be encoded as CNF in practice, have only exponential size CNF representations. To avoid this effect, one usually introduces nondeterministic variables. For example, whereas the minimum number of clauses in a CNF …

In MAXSPACE, given a set of ads $$\mathcal {A}$$ A , one wants to schedule a subset $${\mathcal {A}'\subseteq \mathcal {A}}$$ A ′ ⊆ A into K slots $${B_1, \dots , B_K}$$ B 1 , ⋯ , B K of size L. Each ad $${A_i \in \mathcal {A}}$$ A i ∈ A has a …

The descriptional complexity of basic operations on regular languages using 1-limited automata, a restricted version of one-tape Turing machines, is investigated. When simulating operations on deterministic finite automata with deterministic …

Studies of issues related to computability and computational complexity involve the use of a model of computation. Central in such a model are computational processes. Processes of this kind can be described using an imperative process algebra …

The homogeneous weight (metric) is useful in the construction of codes over a ring of integers $$\mathbb {Z}_{p^l}$$ Z p l (p prime and $$l \ge 1$$ l ≥ 1 an integer). It becomes Hamming weight when the ring is taken to be a finite field and …

We introduce the infix inclusion problem of two languages S and T that decides whether or not S is a subset of the set of all infixes of T. This problem is motivated by the need for identifying malicious computation patterns according to their …

The rational index $$\rho _L$$ ρ L of a language L is an integer function, where $$\rho _L(n)$$ ρ L ( n ) is the maximum length of the shortest string in $$L \cap R$$ L ∩ R , over all regular languages R recognized by n-state nondeterministic …

We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, the edges of the input graph $$G = (V,E)$$ G = ( V , E ) are given as a …

We show that any Boolean function with approximate rank r can be computed by bounded-error quantum protocols without prior entanglement of complexity $$O( \sqrt{r} \log r)$$ O ( r log r ) . In addition, we show that any Boolean function with …

Word equations are equations $$\alpha \doteq \beta $$ α ≐ β where $$\alpha $$ α and $$\beta $$ β are words consisting of letters from some alphabet $$\Sigma $$ Σ and variables from a set X. Recently, there has been substantial interest in the …

We provide a polynomial-time algorithm for b -Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva …

It is shown that the subgroup membership problem for a virtually free group can be decided in polynomial time when all group elements are represented by so-called power words, i.e., words of the form $$p_1^{z_1} p_2^{z_2} \cdots p_k^{z_k}$$ p 1 z …

Parametric timed automata (PTA) have been introduced by Alur, Henzinger, and Vardi as an extension of timed automata in which clocks can be compared against parameters. The reachability problem asks for the existence of an assignment of the …

For a size parameter s : ℕ → ℕ $s:\mathbb {N}\to \mathbb {N}$ , the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}n →{0,1} (represented by a string of …

In k-Digraph Coloring we are given a digraph and are asked to partition its vertices into at most k sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) k-Coloring, but becomes trivial if the …