Olga Martynova

According to our database, Olga Martynova authored at least 11 papers between 2020 and 2024.

Collaborative distances:

• Dijkstra number of five.
• Erdős number of four.

2024

Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs.

Olga Martynova

Inf. Comput., January, 2024

2023

Homomorphisms and inverse homomorphisms on graph-walking automata.

Olga Martynova, Alexander Okhotin

Theor. Comput. Sci., November, 2023

Non-closure under complementation for unambiguous linear grammars.

Olga Martynova, Alexander Okhotin

Inf. Comput., June, 2023

State complexity of transforming graph-walking automata to halting, returning and reversible.

Olga Martynova, Alexander Okhotin

Inf. Comput., March, 2023

A Time to Cast Away Stones.

Olga Martynova, Alexander Okhotin

Proceedings of the Implementation and Application of Automata, 2023

Shortest Accepted Strings for Two-Way Finite Automata: Approaching the 2ⁿ Lower Bound.

Olga Martynova, Alexander Okhotin

Proceedings of the Descriptional Complexity of Formal Systems, 2023

2022

The maximum length of shortest accepted strings for direction-determinate two-way finite automata.

Olga Martynova, Alexander Okhotin

CoRR, 2022

Homomorphisms on Graph-Walking Automata.

Olga Martynova, Alexander Okhotin

Proceedings of the Implementation and Application of Automata, 2022

2021

Lower Bounds for Graph-Walking Automata.

Olga Martynova, Alexander Okhotin

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

State Complexity of Union and Intersection on Graph-Walking Automata.

Olga Martynova, Alexander Okhotin

Proceedings of the Descriptional Complexity of Formal Systems, 2021

2020

State complexity of halting, returning and reversible graph-walking automata.

Olga Martynova, Alexander Okhotin

CoRR, 2020