2026-08-21T17:31:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27450 2026-08-21T14:42:40Z ddc:004 open_access

On the Size Complexity of Two-Way Finite Automata with Drop-Once Pebbles Kipriyanov, Georgy Okhotin, Alexander Finite automata two-way automata pebble automata determinization A two-way finite automaton with drop-once pebbles (O. Martynova, A. Okhotin, "A time to cast away stones: On a family of pebble automata", IJFCS, 37 (2026)) may drop its pebbles at any squares of the tape, but a pebble once dropped cannot be moved anymore. In this paper, it is proved that transforming an n-state deterministic automaton with k drop-once pebbles to a standard two-way deterministic finite automaton (2DFA) requires Θ(n^{k+1}) states in the worst case. For nondeterministic two-way automata with one drop-once pebble, it is proved that transforming them to a 2DFA requires at least 2^{n/3-o(n)} states, transforming to a two-way nondeterministic automaton (2NFA) takes at least 2^{n/6-o(n)} states, and, finally, determinizing them to a deterministic two-way automaton with one drop-once pebble requires at least 2^{n/6-o(n)} states. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Georgy Kipriyanov and Alexander Okhotin 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.68 urn:nbn:de:0030-drops-274500 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.68 eng https://creativecommons.org/licenses/by/4.0/legalcode