### ?

## Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems

P. 150-162.

Keywords: data structurescomputational modellingmachineryemptiness problemAutomata-based modelAuxiliary data structuresData structure languageLog spaceTwo-way finite automataTuring machines

Publication based on the results of:

Andriyanets V., Tyers F. M., , in : Proceedings of the Workshop on Computational Modeling of Polysynthetic Languages. : Santa Fe : Association for Computational Linguistics, 2018. P. 31-40.

Added: December 13, 2018

Зуев А. Б., Pokatovich E., Levina E., Вестник Волгоградского государственного университета. Серия 3: Экономика. Экология 2016 № 4 (37) С. 115-129

Automotive industry is among the top priorities in Russia from the perspective of non-oil export development. It appears to be very timely to evaluate its export potential due to a significant contraction of the Russian car market and excessive idle capacity of the industry. The paper is based on international Export Decision Support Models and ...

Added: March 13, 2017

Turovets J., Vishnevskiy K., Engineering Management in Production and Services 2019 No. 11 (4) P. 7-22

digital transformation of other industries. The extant literature sparsely describes
pathways of different sectors in digitalisation, considering the heterogeneous
characteristics of firms and sectors. Emerging economies with important state
participation represent a particular interest in this area of research. To this end,
a multiple case study method was used to describe a set of determinants revealed
from the literature on ...

Added: November 29, 2019

Springer, 2019

Added: August 4, 2019

Krasovskaya S., MacInnes W., Vision 2019 Vol. 3 No. 4 P. 1-24

The seminal model by Laurent Itti and Cristoph Koch demonstrated that we can compute the entire flow of visual processing from input to resulting fixations. Despite many replications and follow-ups, few have matched the impact of the original model - so what made this model so groundbreaking? We have selected five key contributions that distinguish ...

Added: October 13, 2019

Галимуллин М. Ф., Kalishenko E., Рапоткин Н. А., Известия Санкт-Петербургского государственного электротехнического университета ЛЭТИ 2016 № 7 С. 13-23

Deals with the development of threads synchronizing strategies based on the creation of concurrent «flat-combining» data structures as well as research of their performance. The paper considers «flat-combining» approach and its implementation in the library libcds, the development of thread synchronization strategy and its possible implementations. The efficiency of synchronization strategies usage is researched on ...

Added: November 1, 2018

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

Maxim Babenko, Gawrychowski P., Kociumaka T. et al., Theoretical Computer Science 2016 Vol. 638 P. 112-121

We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length . n. For the minimal suffix problem we show that for every . τ, . 1≤τ≤logn, there exists a linear-space data structure with . O(τ) query time and . O(nlogn/τ) preprocessing time. As a ...

Added: October 8, 2015

Santa Fe : Association for Computational Linguistics, 2018

Added: December 13, 2018

Babenko M. A., Kolesnichenko I., Smirnov I., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 637-646

Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an “optimal” extract-min operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the minimum. Extracting all elements faster is impossible as ...

Added: December 6, 2019

Kucherov G., Nekrich Y., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7354: Proceedings of the 23rd Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2012. P. 196-207.

We study a new variant of the string matching problem called {\em cross-document string 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, ...

Added: October 30, 2013

Полякова О. А., Пермь : Издательство Пермского национального исследовательского политехнического университета, 2019

The article deals with the application of the basic principles of structured programming in complex programs systems in the high-level language C ++, which are demonstrated on meaningful examples. ...

Added: August 31, 2020

Babenko M. A., Gawrychowski P., Kociumaka T. et al., , in : Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. : San Diego : SIAM, 2015. P. 572-591.

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size ω ≤ n, our method builds the wavelet tree in O(n log ω √log n) time, improving upon the state-of-the-art algorithm ...

Added: October 4, 2014

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

Springer, 2019

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

Added: October 26, 2021

Berlin : Springer, 2012

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns ...

Added: October 30, 2013

Vyalyi M., Rubtsov A. A., Information and Computation 2021 Vol. 281 Article 104797

We consider a computational model which is known as set automata. The set automata are one-way finite automata with additional storage-the set. There are two kinds of set automata-deterministic (DSA's) and nondeterministic (NSA's). The model was introduced by Kutrib, Malcher, Wendlandt in 2014. It was shown that DSA-recognizable languages look similar to DCFL's and NSA-recognizable ...

Added: February 2, 2022

Babkina T. S., Demidovskij A., Babkin E., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143-155

This paper presents two new approaches to solving a classical NP-hard problem of maximum clique problem (MCP), which frequently arises in the domain of information management, including design of database structures and big data processing. In our research, we are focusing on solving that problem using the paradigm of artificial neural networks. The first approach ...

Added: October 3, 2018

Berlin, Heidelberg : Springer, 2017

The 12th issue of LNCS Transactions on Petri Nets and Other Models of Concurrency (ToPNoC) contains revised and extended versions of a selection of the best papers from the workshops held at the 37th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2016, Toruń, Poland, 19–24 June 2016), and the ...

Added: September 27, 2017

Novikov N., Гуткин Б. С., Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 2016 Vol. 94 No. 5 P. 052313-1-052313-13

We study the behavior of a minimal model of synaptically sustained persistent activity that consists of two quadratic integrate-and-fire neurons mutually coupled via excitatory synapses. Importantly, each of the neurons is excitable, as opposed to an oscillator; hence when uncoupled it sits at a subthreshold rest state. When the constituent neurons are mutually coupled via ...

Added: October 22, 2017

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

Babenko A., Lempitsky V., , in : Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2012). : Providence : IEEE, 2012. P. 3069-3076.

A new data structure for efficient similarity search in very large dataseis of high-dimensional vectors is introduced. This structure called the inverted multi-index generalizes the inverted index idea by replacing the standard quantization within inverted indices with product quantization. For very similar retrieval complexity and preprocessing time, inverted multi-indices achieve a much denser subdivision of ...

Added: October 1, 2014

MacInnes W., Hunt A., Clarke A. et al., Cognitive Computation 2018 Vol. 10 No. 5 P. 703-717

Background Used / introduction
of The early eye tracking studies of descriptive Yarbus Provided Evidence That an observer's task Influences
patterns of eye Movements, a leading to the a tantalizing prospect That an observer's Intentions Could the BE
inferred from Their saccade behavior. This is a
dynamic and dynamic cognitive companion
using a Dynamic Bayesian Network (DBN). Understanding how it
comes ...

Added: May 8, 2018

Springer, 2014

This book constitutes the proceedings of the 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014, held in Ouro Preto, Brazil, in October 2014. The 20 full and 6 short papers included in this volume were carefully reviewed and selected from 45 submissions. The papers focus not only on fundamental algorithms in string ...

Added: October 4, 2014