2 papers
cs.CC2020
Lower Bounds for Semi-adaptive Data Structures via Corruption
Pavel Dvořák, Bruno Loff
In a dynamic data structure problem we wish to maintain an encoding of some data in memory, in such a way that we may efficiently carry out a sequence of queries and updates to the…
cs.FL2019
The computational power of parsing expression grammars
Bruno Loff, Nelma Moreira, Rogério Reis
We study the computational power of parsing expression grammars (PEGs). We begin by constructing PEGs with unexpected behaviour, and surprising new examples of languages with PEGs,…