Cookies
O website necessita de alguns cookies e outros recursos semelhantes para funcionar. Caso o permita, o INESC TEC irá utilizar cookies para recolher dados sobre as suas visitas, contribuindo, assim, para estatísticas agregadas que permitem melhorar o nosso serviço. Ver mais
Aceitar Rejeitar
  • Menu
Tópicos
de interesse
Detalhes

Detalhes

  • Nome

    Bruno Serra Loff
  • Cluster

    Informática
  • Cargo

    Investigador Sénior
  • Desde

    01 março 2017
Publicações

2021

Hardness of Constant-round Communication Complexity

Autores
Hirahara, S; Ilango, R; Loff, B;

Publicação
Electron. Colloquium Comput. Complex.

Abstract

2020

The computational power of parsing expression grammars

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

Publicação
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

2020

Lower Bounds for Semi-adaptive Data Structures via Corruption

Autores
Dvorák, P; Loff, B;

Publicação
CoRR

Abstract

2020

NP-Hardness of Circuit Minimization for Multi-Output Functions

Autores
Ilango, R; Loff, B; Oliveira, IC;

Publicação
Electronic Colloquium on Computational Complexity (ECCC)

Abstract

2019

Lifting Theorems for Equality

Autores
Loff, B; Mukhopadhyay, S;

Publicação
Electronic Colloquium on Computational Complexity (ECCC)

Abstract