Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
Interest
Topics
Details

Details

Publications

2020

The computational power of parsing expression grammars

Authors
Loff, B; Moreira, N; Reis, R;

Publication
Journal of Computer and System Sciences

Abstract
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, including the language of palindromes whose length is a power of two, and a binary-counting language. We then propose a new computational model, the scaffolding automaton, and prove that it exactly characterises the computational power of parsing expression grammars (PEGs). Several consequences will follow from this characterisation: (1) we show that PEGs are computationally “universal”, in a certain sense, which implies the existence of a PEG for a P-complete language; (2) we show that there can be no pumping lemma for PEGs; and (3) we show that PEGs are strictly more powerful than online Turing machines which do o(n/(log?n)2) steps of computation per input symbol. © 2020

2019

Lifting Theorems for Equality

Authors
Loff, B; Mukhopadhyay, S;

Publication
Electronic Colloquium on Computational Complexity (ECCC)

Abstract

2019

Simulation Theorems via Pseudo-random Properties

Authors
Chattopadhyay, A; Koucky, M; Loff, B; Mukhopadhyay, S;

Publication
COMPUTATIONAL COMPLEXITY

Abstract
We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403-435, 1999), to any gadget which satisfies a certainhitting property. We prove that inner product and gap-Hammingsatisfy this property, and as a corollary, we obtain a deterministic simulationtheorem for these gadgets, where the gadget's input size is logarithmicin the input size of the outer function. This yields the firstdeterministic simulation theorem with a logarithmic gadget size, answeringan open question posed by Goos, Pitassi & Watson (in: Proceedingsof the 56th FOCS, 2015). Our result also implies the previous results for the indexing gadget, withbetter parameters than was previously known. Moreover, a simulationtheorem with logarithmic-sized gadget implies a quadratic separationin the deterministic communication complexity and the logarithm ofthe 1-partition number, no matter how high the 1-partition number iswith respect to the input size-something which is not achievable by previous results of Goos, Pitassi & Watson (2015).

2018

Catalytic Space: Non-determinism and Hierarchy

Authors
Buhrman, H; Koucký, M; Loff, B; Speelman, F;

Publication
Theory Comput. Syst.

Abstract
Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation. Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation. © Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman; licensed under Creative Commons License CC-BY.

2018

Simulation Beats Richness: New Data-Structure Lower Bounds

Authors
Chattopadhyay, A; Koucky, M; Loff, B; Mukhopadhyay, S;

Publication
Electronic Colloquium on Computational Complexity (ECCC)

Abstract