The outlook for mathematics on the web.
The partial inverse minimum cut problem with L1-norm is strongly NP-hard
The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted L1-norm. We prove that the problem remains hard for the unweighted case and show that the NP-hardness proof of Yang [RAIRO-Oper. Res.35 (2001) 117–126] for this problem with additional bound...
The passing of a rational expression to a nondeterministic finite automaton. (Passage d'une expression rationnelle à un automate fini non-déterministe.)
The PCP theorem
The performance profile: A multi-criteria performance evaluation method for test-based problems
In test-based problems, solutions produced by search algorithms are typically assessed using average outcomes of interactions with multiple tests. This aggregation leads to information loss, which can render different solutions apparently indifferent and hinder comparison of search algorithms. In this paper we introduce the performance profile, a generic, domain-independent, multi-criteria performance evaluation method that mitigates this problem by characterizing the performance of a solution by...
The polar form of a polynomial surface.
The present and future of signal processing
The problems of complexity of almost context-free languages [Abstract of thesis]
The pseudovariety is hyperdecidable
The pseudovariety of semigroups of triangular matrices over a finite field
We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it.
The pseudovariety of semigroups of triangular matrices over a finite field
We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it.
The quantitative evaluation of image quality and definition of an image
The quantum size and waiting time for time-shared systems
The range of non-linear natural polynomials cannot be context-free
Suppose that some polynomial with rational coefficients takes only natural values at natural numbers, i. e., . We show that the base- representation of is a context-free language if and only if is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma.
The reduction of binary trees by means of an input-restricted deque
The relation of two patterns with comparable languages patterns
The role of rudimentary relations in complexity theory
The Rooted Tree Embedding Problem into Points in the Plane.
The rupture degree and gear graphs.
The second machine class 2, an encyclopedic view on the parallel computation thesis