### ?

## Regular realizability problems and context-free languages

P. 25-27.

Rubtsov Alexander

Language:
English

### In book

Ekaterinburg : Ural Fedearal University, 2014

Rubtsov A. A., Vyalyi M., , in : Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Vol. 10846.: Springer, 2018. P. 295-307.

We consider a computational model which is known as set automata.
The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].
In this ...

Added: June 21, 2018

Rubtsov A. A., Vyalyi M., , in : Descriptional Complexity of Formal Systems. Vol. 9118.: Switzerland : Springer, 2015. P. 256-267.

We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse ...

Added: August 25, 2015

Rubtsov A. A., Vyalyi M., , in : Developments in Language Theory 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. : Cham : Springer, 2017. P. 332-344.

We consider a computational model which is known as set automata. The set automata are one-way finite automata with an additional storage---the set. There are two kinds of set automata---the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by M. Kutrib, A. Malcher, M. Wendlandt in ...

Added: September 5, 2017

Vyalyi M., Rubtsov A. A., Проблемы передачи информации 2015 Т. 51 № 4 С. 47-59

We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance ...

Added: February 14, 2016

Yaroslav Shitov, Linear Algebra and its Applications 2013 Vol. 439 No. 8 P. 2500-2502

We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute. ...

Added: August 11, 2013

Shitov Y., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77

We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...

Added: February 23, 2016

Malyshev D., Pardalos P. M., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612

The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called ...

Added: December 18, 2015

Malyshev D., Journal of Applied and Industrial Mathematics 2013 Vol. 7 No. 2 P. 221-228

The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by ...

Added: June 23, 2013

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

Malyshev D., Journal of Applied and Industrial Mathematics 2012 Vol. 6 No. 1 P. 97-99

Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs, On the other ...

Added: December 7, 2012

Aleskerov F. T., Meshcheryakova N., Shvydun S. et al., , in : 6th International Conference on Computers Communications and Control (ICCCC) 2016. : Oradea : Agora University, 2016. P. 118-123.

The problem of quick detection of central nodes in large networks is studied. There are many measures that allow to evaluate a topological importance of nodes of the network. Unfortunately, most of them cannot be applied to large networks due to their high computational complexity. However, if we narrow the initial network and apply these ...

Added: June 8, 2016

Cham : Springer, 2017

The 21st International Conference on Developments in Language Theory (DLT 2017) was organized by the Department of Mathematics of the University of Liège, Belgium, during August 7–11, 2017.
The DLT conference series is one of the major international conference series in language theory and related areas. The DLT conference was established by G. Rozenberg and A. ...

Added: September 5, 2017

Rybakov M., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 2 P. 426-443

It is shown that products and expanding relativized products of propositional modal logics where one component is the minimal monomodal logic K are polynomial-time reducible to their single-variable fragments. Therefore, the nown lower bound complexity and undecidability results for such logics are extended to their single-variable fragments. Similar results are obtained for products where one component is a polymodal logic with a K-style ...

Added: September 24, 2020

Korpelainen N., Lozin V. V., Malyshev D. et al., Theoretical Computer Science 2011 No. 412 P. 3545-3554

The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle ...

Added: September 11, 2012

Malyshev D., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.

The coloring problem is studied in the paper for graph classes deﬁned by two small forbidden induced subgraphs. We prove some suﬃcient conditions for eﬀective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most ﬁve vertices except ...

Added: October 3, 2013

Rubtsov A. A., , in : Proceedings of Language and Automata Theory and Applications 2020. : Springer, 2020.

Formal grammars provide the way of formal language's description. The other way is describing a language by automata model. But not all classes of formal languages fit in the both ways of description. We provide a new way of formal language's description which is universal and combine the advantages of the both mentioned methods — a ...

Added: October 19, 2017

Malyshev D., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. ...

Added: April 7, 2014

Mokeev D. B., Malyshev D., Optimization Letters 2020 Vol. 14 No. 6 P. 1317-1322

For a graph G and a positive integer k, a subset C of vertices of G is called a k-path vertex cover if C intersects all paths of k vertices in G. The cardinality of a minimum k-path vertex cover is denoted by β_{P_k}(G). For a graph G and a positive integer k, a subset ...

Added: March 12, 2020

Sirotkin D., Malyshev D., Journal of Applied and Industrial Mathematics 2018 Vol. 12 No. 4 P. 759-769

The 3-coloring problem for a given graph consists in verifying whether it is possible
to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete
complexity classification is known for this problem for the hereditary classes defined by triples of
forbidden induced subgraphs, each on at most 5 vertices. In this article, ...

Added: November 20, 2018

Malyshev D., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630

The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for ...

Added: November 25, 2012

Alekseev V., Lozin V. V., Malyshev D. et al., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107

We study the computational complexity of finding a maximum independent set of vertices in a planar graph. In general, this problem is known to be NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify a graph parameter to which the complexity of the problem is sensible and produce a number of both negative ...

Added: November 7, 2012

Sirotkin D., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205

The vertex 3-colourability problem is to determine for a given graph whether one can divide its vertex set into three subsets of pairwise non-adjacent vertices. This problem is NP-complete in the class of planar graphs, but it becomes polynomial-time solvable for planar triangulations, i.e. planar graphs, all facets of which (including external) are triangles. Additionally, ...

Added: July 2, 2018

Complexity function and complexity of validity of modal and superintuitionistic propositional logics

Rybakov M., Shkatov D., Journal of Logic and Computation 2023

We consider the relationship between the algorithmic properties of the validity problem for a modal or superintuitionistic propositional logic and the size of the smallest Kripke countermodels for non-theorems of the logic. We establish the existence, for every degree of unsolvability, of a propositional logic whose validity problem belongs to the degree and whose every ...

Added: January 6, 2023

Malyshev D., Journal of Applied and Industrial Mathematics 2020 Vol. 14 No. 4 P. 706-721

The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...

Added: January 30, 2021