3 citations · 9 across the 7 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.FL2022★ 1 cited
The Simplest Proof of Parikh's Theorem via Derivation Trees
Alexander Rubtsov
Parikh's theorem is a fundamental result of the formal language's theory. There had been published many proofs and many papers claimed to provide a simplified proof, but most of th…
cs.FL2022
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems
Alexander Rubtsov, Mikhail Vyalyi
We consider general computational models: one-way and two-way finite automata, and logarithmic space Turing machines, all equipped with an auxiliary data structure (ADS). The defin…