Computing median and antimedian sets in median graphs

The median (antimedian) set of a profile π=(u ₁,…,u _k ) of vertices of a graph G is the set of vertices x that minimize (maximize) the remoteness ∑ _i d(x,u _i ). Two algorithms for median graphs G of complexity O(n idim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes.     

Left-forbidding cooperating distributed grammar systems

A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.     

Multi-view Superpixel Stereo in Urban Environments

Urban environments possess many regularities which can be efficiently exploited for 3D dense reconstruction from multiple widely separated views. We present an approach utilizing properties of piecewise planarity and restricted number of plane orientations to suppress reconstruction and matching ambiguities causing failures of standard dense stereo methods. We formulate the problem of the 3D reconstruction in MRF framework built on an image pre-segmented into superpixels. Using this representation, we propose novel photometric and superpixel boundary consistency terms explicitly derived from superpixels and show that they overcome many difficulties of standard pixel-based formulations and handle favorably problematic scenarios containing many repetitive structures and no or low textured regions. We demonstrate our approach on several wide-baseline scenes demonstrating superior performance compared to previously proposed methods.     

The <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>-Optimality of the IIPG Method for Odd Degrees of Polynomial Approximation in 1D

The paper deals with a numerical analysis of the incomplete interior penalty Galerkin (IIPG) method applied to one dimensional Poisson problem. Based on a particular choice of the interior penalty parameter σ (order of O(h ⁻¹)), we derive the optimal error estimate in the L ²-norm for odd degrees of polynomial approximation for locally quasi-uniform meshes. Moreover, we show that only the mentioned choice of the penalty parameter leads to optimal orders of convergence. Finally, presented numerical experiments verify the theoretical results.     

Adsorption–desorption noise in plasmonic chemical/biological sensors for multiple analyte environment

We investigated intrinsic noise in plasmonic sensors caused by adsorption and desorption of gaseous analytes on the sensor surface. We analyzed a general situation when there is a larger number of different analyte species. We applied our model to calculate various analyte mixtures, including some environmental pollutants, toxic and dangerous substances. The spectral density of mean square refractive index fluctuations follows a dependence similar to that of generation-recombination noise in photodetectors, flat at lower frequencies and sharply decreasing at higher. Some of the calculated noise levels are well within the detection range of conventional surface plasmon resonance sensors. An AD noise peak is observed in temperature dependence of mean square refractive index fluctuations, thus sensor operating temperature may be optimized to obtain larger signal to noise ratio. A significant property of AD noise is its rise with the decreasing plasmon sensor area, which means that it will be even more pronounced in modern nanoplasmonic devices. Our consideration is valid both for conventional surface plasmon resonance devices and for general nanoplasmonic devices.     

Complexity classes for self-assembling flexible tiles

We present a theoretical model for self-assembling DNA tiles with flexible branches. We encode an instance of a “problem” as a pot of such tiles for which a “solution” is an assembled complete complex without any free sticky ends. Using the number of tiles in an assembled complex as a measure of complexity we show how NTIME classes (such as NP and NEXP) can be represented with corresponding classes of the model.