Olga Martynova

21 papers A* 1A 1C 4Journal 13Unranked 2

Year	Rank	Type	Title / 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