3 papers
cs.FL2025
A Linear-time Simulation of Deterministic -Limited Automata
Alexander Rubtsov
A -limited automaton is a Turing machine that may rewrite each input cell at most~ times. Hibbard (1967) showed that for every 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…
cs.NI2024
Efficient Mixed Integer Linear Programming Approaches to Dynamic Path Restoration
Alexander Rubtsov, Bruno Bauwens, Dmitri Shmelkin +2
We consider the problem of single link failure in an elastic optical network, (also known as flex-grid WDM network). The task is to reroute optical connections that go through the…