### ?

## Minimal Discriminating Words Problem Revisited

P. 129-140.

Kucherov G., Nekrich Y., Gawrychowski P., Starikovskaya T.

We revisit two variants of the problem of computing minimal discriminating words studied in [5]. Given a pattern P and a threshold d, we want to report (i) all shortest extensions of P which occur in less than d documents, and (ii) all shortest extensions of P which occur only in d selected documents. For the rst problem, we give an optimal solution with constant time per output word. For the second problem, we propose an algorithm with running time O(jPj + d (1 + output)) improving the solution of [5].

Language:
English

### In book

Vol. 8214: Proceedings of the 20th Symposium on String Processing and Information Retrieval. , Berlin : Springer, 2013

Vildhoj H. W., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2013. P. 223-234.

Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string $S$ can be computed in linear time and space by constructing a suffix tree or a suffix array of $S$. Here we consider the case when ...

Added: October 30, 2013

Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7464: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science.: Berlin : Springer, 2012. P. 789-799.

We present an algorithm which computes the Lempel-Ziv factorization of a word $W$ of length $n$ on an alphabet $\Sigma$ of size $\sigma$ online in the following sense: it reads $W$ starting from the left, and, after reading each $r = O(\log_{\sigma}{n})$ characters of $W$, updates the Lempel-Ziv factorization. The algorithm requires $O(n\log\sigma)$ bits of ...

Added: October 30, 2013

Babenko M., Kolesnichenko I., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2013. P. 28-37.

Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string S can be computed in linear time and space by constructing a suffix tree or a suffix array of S. Here we consider the case when ...

Added: October 30, 2013

Kopelowitz T., Kucherov G., Nekrich Y. et al., Journal of Discrete Algorithms 2013

We study a new variant of the pattern matching problem called cross-document pattern matching, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear ...

Added: October 30, 2013

Kucherov G., Nekrich Y., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7608: Proceedings of the 19th International Symposium on String Processing and Information Retrieval.: Berlin : Springer, 2012. P. 307-317.

We study the following three problems of computing generic or discriminating words for a given collection of documents. Given a pattern $P$ and a threshold $d$, we want to report (i) all longest extensions of $P$ which occur in at least $d$ documents, (ii) all shortest extensions of $P$ which occur in less than $d$ ...

Added: October 30, 2013

Konstantin Bazhanov, Obiedkov S., Annals of Mathematics and Artificial Intelligence 2014 Vol. 70 No. 1-2 P. 5-24

In this paper, we consider algorithms involved in the computation of the Duquenne–Guigues basis of implications. The most widely used algorithm for constructing the basis is Ganter’s Next Closure, designed for generating closed sets of an arbitrary closure system. We show that, for the purpose of generating the basis, the algorithm can be optimized. We ...

Added: October 26, 2013

Berlin, Heidelberg : Springer, 2013

This volume contains the papers presented at the 6th International Conference on Similarity Search and Applications (SISAP 2013), held at A Coruna, Spain, during October 2–4, 2013. The International Conference on Similarity Search and Applications (SISAP) is an annual forum for researchers and application developers in the area of similarity data management. It aims at the technological problems shared ...

Added: September 27, 2013

Cham : Springer, 2018

This book constitutes the refereed proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, held in Krems, Austria, in January/February 2018.
The 48 papers presented in this volume were carefully reviewed and selected from 97 submissions. They were organized in topical sections named: foundations of computer science; ...

Added: March 1, 2018

Bliznets Ivan, Cygan M., Komosa P. et al., , in : Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. : SIAM, 2016. P. 1132-1151.

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper IntervalCompletion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds ...

Added: October 31, 2018

Соколов Б. В., Ivanov D., Dolgui A., Algorithms 2018 Vol. 11 No. 5 P. 57

Added: February 11, 2020

Springer, 2020

This special issue of Theory of Computing Systems consists of extended journal papers originally presented at the 13th International Computer Science Symposium in Russia (CSR 2018) held on June 6–10, 2018 in Moscow, Russia. The event was hosted by National Research University Higher School of Economics and chaired by Vladimir V. Podolskii. Preliminary versions of ...

Added: October 27, 2020

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019

Added: November 13, 2019

NY : Springer, 2013

Information systems have been developed in parallel with computer science, although information systems have roots in different disciplines including mathematics, engineering, and cybernetics. Research in information systems is by nature very interdisciplinary. As it is evidenced by the chapters in this book, dynamics of information systems has several diverse applications. The book presents the state-of-the-art ...

Added: December 12, 2013

Voskov L., Efremov S. G., В кн. : Distributed computer and communication networks: control, computation, communications (DCCN-2013). : М. : Техносфера, 2013. С. 197-199.

In this paper we propose models and algorithms for increasing lifetime of dynamically reconfigurable wireless sensor networks with a mobile sink and anonymous power supplies. A new definition and assessment model of a network lifetime in case of dynamic reconfiguration are given. We propose a new method for dynamic reconfiguration aimed at finding an optimal ...

Added: February 12, 2014

Delong A., Osokin A., Isack H. et al., , in : Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010). : San Francisco : IEEE, 2010. P. 2173-2180.

The α-expansion algorithm [4] has had a significant impact in computer vision due to its generality, effectiveness, and speed. Thus far it can only minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main contribution is to extend α-expansion so that it can simultaneously optimize “label costs” as well. An energy with label ...

Added: October 18, 2017

Springer, 2019

16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings ...

Added: October 26, 2021

Babenko M. A., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 5010: Proceedings of the Third International Computer Science Symposium in Russia.: Berlin : Springer, 2008. P. 64-75.

Given a set of $N$ strings $A = \set{\alpha_1, \ldots, \alpha_N}$ of total length $n$ over alphabet~$\Sigma$ one may ask to find, for a fixed integer $K$, $2 \le K \le N$, the longest substring $\beta$ that appears in at least $K$ strings in $A$. It is known that this problem can be solved in ...

Added: October 30, 2013

Babenko M. A., Goldberg A. V., Gupta A. ,. et al., ACM Transactions on Algorithms 2016 Vol. 13 No. 1 P. 16:1-16:17

We consider the hub label optimization problem, which arises in designing fast preprocessing-based shortest- path algorithms. We give O(log n)-approximation algorithms for the objectives of minimizing the maximum label size (l∞-norm) and simultaneously minimizing a constant number of lp-norms. Prior to this, an O(log n)- approximation algorithm was known [Cohen et al. 2003] only for ...

Added: January 12, 2017

M. Polyakova, Semenov A. V., Kovalyuk V. et al., IEEE Transactions on Applied Superconductivity 2019 Vol. 29 No. 5 P. 1-5

We present a simple quantum detector tomography
protocol, which allows, without ambiguities, to measure the twospot
detection efficiency and extract the hot-spot interaction length
of SNSPDs with unity intrinsic detection efficiency. We identify a
significant parasitic contribution to the measured two-spot efficiency,
related to an effect of the bias circuit, and find a way to rule
out this contribution during data ...

Added: October 23, 2019

МГУ, МАКС Пресс, 2018

The proceedings of the tenth international conference "Discrete Models in Control Systems Theory" (Moscow and Moscow Region, May 23-25, 2018) includes 100 papers on such topics as discrete functional systems, properties of discrete functions, synthesis and complexity of control systems, reliability, control and diagnostics of control systems, automata, graph theory, combinatorics, coding theory, mathematical methods ...

Added: June 14, 2018

Kolpakov R. M., Kucherov G., Starikovskaya T., , in : Proceedings of the First International Conference on Data Compression, Communications and Processing. : NY : IEEE Computer Society, 2013. P. 92-97.

We consider a compact text index based on evenly spaced sparse suffix trees of a text \cite{KU-96}. Such a tree is defined by partitioning the text into blocks of equal size and constructing the suffix tree only for those suffixes that start at block boundaries. We propose a new pattern matching algorithm on this structure. ...

Added: October 30, 2013

Edward Elgar Publishing, 2019

The digital economy is gradually gaining traction through a variety of recent technological developments, including the introduction of the Internet of things, artificial intelligence and markets for data. This innovative book contains contributions from leading competition law scholars who map out and investigate the anti-competitive effects that are developing in the digital economy. ...

Added: August 4, 2020

Popkov Y., Dubnov Y. A., Popkov A. Y., Automation and Remote Control 2018 Vol. 79 No. 11 P. 2038-2051

The direct and inverse projections (DIP) method was proposed to reduce the feature space to the given dimensions oriented to the problems of randomized machine learning and based on the procedure of “direct” and “inverse” design. The “projector” matrices are determined by maximizing the relative entropy. It is suggested to estimate the information losses by ...

Added: February 12, 2019