### ?

## Descriptional Complexity of Formal Systems

Vol. 9118.
Switzerland:
Springer, 2015.

Under the general editorship: Shallit J., Okhotin A.

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

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

Springer, 2020

Added: October 22, 2018

Rubtsov A. A., Vyalyi M., Information and Computation 2019

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 ...

Added: October 22, 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

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

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

Bresolin D., Tvardovskii A., Evtushenko N. V. et al., , in: IFAC-PapersOnLine (T.V.51.Вып 7). .: Elsevier, 2018.. P. 486-492.

Timed automata and timed finite state machins (TFSMs) have been proposed to represent more accurately the behaviour of systems in continuous time. Recently, we introduced a model of TFSMs that extends the expressive power of FSMs by introducing a single clock, timed guards which restrict when the input/output transitions may happen, and timeouts on the ...

Added: November 1, 2018

Rubtsov A. A., , in: Abstracts of Reports and other materials of the 7th School "Computer Science Days in Ekaterinburg". .: Ekaterinburg: Ural Fedearal University, 2014.. P. 25-27.

Added: October 17, 2014

Ekaterinburg: Ural Fedearal University, 2014

Added: October 17, 2014

Konev B. Y., Lutz C., Wolter F. et al., , in: 25th International Joint Conference on Artificial Intelligence. .: [б.и.], 2016.. P. 1153-1159.

We investigate the problem of conservative rewritability of a TBox T in a description logic (DL) L into a TBox T' in a weaker DL L'. We focus on model-conservative rewritability (T' entails T and all models of T are expandable to models of T'), subsumption-conservative rewritability (T' entails T and all subsumptions in the ...

Added: September 18, 2017

Bienvenu M., Kikot S., Kontchakov R. et al., , in: Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017.. .: Aachen: CEUR Workshop Proceedings, 2017.. P. 1-12.

Our concern is answering ontology-mediated queries (Ο q), whereΟ is a set of linear tgds and q a conjunctive query (CQ) of bounded hypertree width. Assuming that the arity of predicates is bounded, we show that polynomial-size nonrecursive Datalog rewritings can be constructed and executed in (i) LOGCFL for OMQs with ontologies of bounded existential ...

Added: September 18, 2017

Chistikov D., Vyalyi M., , in: LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Saarbrücken, Germany. July, 2020. .: Association for Computing Machinery (ACM), 2020.. P. 312-326.

Consider the following one-player game. Take a well-formed sequence of opening and closing brackets (a Dyck word). As a move, the player can pair any opening bracket with any closing bracket to its right, erasing them. The goal is to re-pair (erase) the entire sequence, and the cost of a strategy is measured by its ...

Added: September 4, 2020

Switzerland: Springer International Publishing, 2021

Added: September 28, 2021

Babash A. V., , in: Proceedings of the 10th International Scientific and Practical Conference named after A. I. Kitov "Information Technologies and Mathematical Methods in Economics and Management (IT&MM-2020)"/, Moscow, Russia, October 15-16, 2020. Vol. 2830.: CEUR Workshop Proceedings, 2021.. P. 337-359.

A trapdoor cipher is a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. In cryptographic practice, there could be situations when a constructed cipher may contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. In this paper, we ...

Added: November 2, 2021

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

Zakharyaschev M., Kikot S., Bienvenu M. et al., , in: Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017.. .: Aachen: CEUR Workshop Proceedings, 2017..

We discuss the parameterised complexity of answering tree-shaped ontology-mediated queries (OMQs) in OWL2QL under various restrictions on their ontologies and conjunctive queries (CQs). In particular, we construct an ontology τ such that answering OMQs (τ, q) with tree-shaped CQs q is W[1]- hard if the number of leaves in q is regarded as the parameter. ...

Added: September 18, 2017

American Association for Artificial Intelligence (AAAI) Press, 2015

Added: September 18, 2017

[б.и.], 2016

Added: September 18, 2017

Zakharyaschev M., Artale A., Kontchakov R. et al., , in: Proceedings of the National Conference on Artificial Intelligence. .: American Association for Artificial Intelligence (AAAI) Press, 2015.. P. 1417-1423.

We design a tractable Horn fragment of the Halpern-Shoham temporal logic and extend it to interval-based temporal description logics, instance checking in which is P-complete for both combined and data complexity. ...

Added: September 18, 2017

Rubtsov A. A., , in: Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. .: Cham: Springer, 2018.. P. 553-565.

We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), ...

Added: September 12, 2018

Botoeva E., Zakharyaschev M., Kontchakov R. et al., , in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015. .: Palo Alto: AAAI Press, 2015.. P. 4240-4246.

Deciding inseparability of description logic knowledge bases (KBs) with respect to conjunctive queries is fundamental for many KB engineering and maintenance tasks including versioning, module extraction, knowledge exchange and forgetting. We study the combined and data complexity of this inseparability problem for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL ...

Added: September 18, 2017

Bienvenu M., Kikot S., Kontchakov R. et al., , in: International Workshop on Description Logics, DL 2016. Issue 1577.: [б.и.], 2016.. P. 1-13.

We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded-leaf tree-shaped conjunctive queries, and (iii) arbitrary ontologies and bounded-leaf tree-shaped conjunctive queries, one can construct and evaluate nonrecursive datalog rewritings by, respectively, LOGCFL, NL and LOGCFL algorithms, ...

Added: September 18, 2017

Cham: Springer, 2018

This volume of Lecture Notes in Computer Science contains the papers presented at the 22nd International Conference on Developments in Language Theory (DLT 2018) organized by the Algorithmic “Oritatami” Self-Assembly Laboratory as part of the 100th Anniversary Commemorative Events of University of Electro-Communications (UEC) in Fuchu, Tokyo, Japan, during September 10–14, 2018.
The DLT conference series is one ...

Added: September 12, 2018