Olga Martynova

21 papers A* 1A 1C 4Journal 13Unranked 2
YearRankTypeTitle / Venue / Authors
2026 J jnl
A Time to Cast Away Stones: On a Family of Pebble Automata.
Int. J. Found. Comput. Sci.
Olga Martynova, Alexander Okhotin
2025 C conf
From Regular Expressions to Deterministic Finite Automata: $2^{\frac{n}{2}+\sqrt{n}(\log n)^{\varTheta (1)}}$ States Are Necessary and Sufficient.
CIAA
Olga Martynova, Alexander Okhotin
2025 J jnl
From regular expressions to deterministic finite automata: $2
CoRR
Olga Martynova, Alexander Okhotin
2025 A* conf
Nondeterministic Tree-Walking Automata Are Not Closed Under Complementation.
ICALP
Olga Martynova, Alexander Okhotin
2024 J jnl
Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs.
Inf. Comput.
Olga Martynova
2024 C conf
Exact Descriptional Complexity of Determinization of Input-Driven Pushdown Automata.
CIAA
Olga Martynova
2024 J jnl
Exact descriptional complexity of determinization of input-driven pushdown automata.
CoRR
Olga Martynova
2024 J jnl
Nondeterministic tree-walking automata are not closed under complementation.
CoRR
Olga Martynova, Alexander Okhotin
2023 C conf
A Time to Cast Away Stones.
CIAA
Olga Martynova, Alexander Okhotin
2023 J jnl
Homomorphisms and inverse homomorphisms on graph-walking automata.
Theor. Comput. Sci.
Olga Martynova, Alexander Okhotin
2023 J jnl
Non-closure under complementation for unambiguous linear grammars.
Inf. Comput.
Olga Martynova, Alexander Okhotin
2023 — conf
Shortest Accepted Strings for Two-Way Finite Automata: Approaching the 2
DCFS
Olga Martynova, Alexander Okhotin
2023 J jnl
State complexity of transforming graph-walking automata to halting, returning and reversible.
Inf. Comput.
Olga Martynova, Alexander Okhotin
2022 J jnl
Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs.
CoRR
Olga Martynova
2022 C conf
Homomorphisms on Graph-Walking Automata.
CIAA
Olga Martynova, Alexander Okhotin
2022 J jnl
Non-closure under complementation for unambiguous linear grammars.
CoRR
Olga Martynova, Alexander Okhotin
2022 J jnl
The maximum length of shortest accepted strings for direction-determinate two-way finite automata.
CoRR
Olga Martynova, Alexander Okhotin
2021 J jnl
Homomorphisms on graph-walking automata.
CoRR
Olga Martynova, Alexander Okhotin
2021 A conf
Lower Bounds for Graph-Walking Automata.
STACS
Olga Martynova, Alexander Okhotin
2021 — conf
State Complexity of Union and Intersection on Graph-Walking Automata.
DCFS
Olga Martynova, Alexander Okhotin
2020 J jnl
State complexity of halting, returning and reversible graph-walking automata.
CoRR
Olga Martynova, Alexander Okhotin