Zobrazeno 1 - 10
of 219
pro vyhledávání: '"Martynova Olga"'
Autor:
Martynova, Olga, Okhotin, Alexander
It is proved that the family of tree languages recognized by nondeterministic tree-walking automata is not closed under complementation, solving a problem raised by Boja\'nczyk and Colcombet ("Tree-walking automata do not recognize all regular langua
Externí odkaz:
http://arxiv.org/abs/2412.02618
Autor:
Martynova, Olga
The number of states and stack symbols needed to determinize nondeterministic input-driven pushdown automata (NIDPDA) working over a fixed alphabet is determined precisely. It is proved that in the worst case exactly 2^{n^2} states are needed to dete
Externí odkaz:
http://arxiv.org/abs/2404.10516
Publikováno v:
E3S Web of Conferences, Vol 274, p 10022 (2021)
The article describes the concept of sustainable development and forms the criteria for sustainable development of the territory. The sustainability of the territory development should be considered from various angles, including industrial and agric
Externí odkaz:
https://doaj.org/article/205b083ecdcc4feeae370f7de9d1003f
Autor:
Martynova, Olga
This paper proves the decidability of the emptiness problem for two models which recognize graphs: graph-walking automata, and tilings of graphs by star subgraphs (star automata). Furthermore, it is proved that the non-emptiness problem for graph-wal
Externí odkaz:
http://arxiv.org/abs/2212.02380
Autor:
Martynova, Olga, Okhotin, Alexander
The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To be precise, a particular unambiguous linear grammar is presented, and
Externí odkaz:
http://arxiv.org/abs/2210.02329
Autor:
Martynova, Olga, Okhotin, Alexander
It is shown that, for every $n \geqslant 2$, the maximum length of the shortest string accepted by an $n$-state direction-determinate two-way finite automaton is exactly $\binom{n}{\lfloor\frac{n}{2}\rfloor}-1$ (direction-determinate automata are tho
Externí odkaz:
http://arxiv.org/abs/2210.00235
Publikováno v:
In International Journal of Psychophysiology January 2025 207
Autor:
Martynova, Olga, Okhotin, Alexander
Graph-walking automata (GWA) are a model for graph traversal using finite-state control: these automata move between the nodes of an input graph, following its edges. This paper investigates the effect of node-replacement graph homomorphisms on recog
Externí odkaz:
http://arxiv.org/abs/2111.10214
Autor:
Kabir, Muhammad Salman a, Kurkin, Semen a, ⁎, Portnova, Galina b, Martynova, Olga b, Wang, Zhen c, Hramov, Alexander a
Publikováno v:
In Chaos, Solitons and Fractals: the interdisciplinary journal of Nonlinear Science, and Nonequilibrium and Complex Phenomena August 2024 185
Autor:
Mitiureva, Dina, Sysoeva, Olga, Proshina, Ekaterina, Portnova, Galina, Khayrullina, Guzal, Martynova, Olga
Publikováno v:
In Psychiatry Research: Neuroimaging August 2024 342