Alexander Rubtsov

collaborators

Showing cs.FLShow all

2 papers · 1 filter

cs.FL2025

A Linear-time Simulation of Deterministic $d$ -Limited Automata

Alexander Rubtsov

A $d$ -limited automaton is a Turing machine that may rewrite each input cell at most~ $d$ times. Hibbard (1967) showed that for every $d \geq 2$ such automata recognize all context-…

cs.FL2024

Computational Model for Parsing Expression Grammars

Alexander Rubtsov, Nikita Chudinov

We present a computational model for Parsing Expression Grammars (PEGs). The predecessor of PEGs top-down parsing languages (TDPLs) were discovered by A. Birman and J. Ullman in th…

A Linear-time Simulation of Deterministic d-Limited Automata

Computational Model for Parsing Expression Grammars

A Linear-time Simulation of Deterministic $d$ -Limited Automata