Publications related to Uniform parsing for hyperedge replacement grammars

Hearing structure in music: An empirical inquiry into listening as representation and processing

As a universal expression of human creativity, music is capable of conveying great subtlety and complexity. Crucially, this complexity is not encoded in the score or in the sounds, but is rather construed in the mind of the listener in the form of nuanced ...

EPFL2024

Interpreting Rhythm as Parsing: Syntactic-Processing Operations Predict the Migration of Visual Flashes as Perceived During Listening to Musical Rhythms

Martin Alois Rohrmeier, Gabriele Cecchetti, Steffen Alexander Herff

Music can be interpreted by attributing syntactic relationships to sequential musical events, and, computationally, such musical interpretation represents an analogous combinatorial task to syntactic processing in language. While this perspective has been ...

Wiley2023

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Karl Aberer, Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Thanh Trung Huynh

Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...

ELSEVIER SCIENCE INC2023

Musical Garden Paths: Evidence for Syntactic Revision Beyond the Linguistic Domain

Martin Alois Rohrmeier, Gabriele Cecchetti, Steffen Alexander Herff

While theoretical and empirical insights suggest that the capacity to represent and process complex syntax is crucial in language as well as other domains, it is still unclear whether specific parsing mechanisms are also shared across domains. Focusing on ...

Wiley2022

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...

IEEE COMPUTER SOC2022

Efficient Parsing with Derivatives and Zippers

Romain Edelmann

Parsing is the process that enables a computer system to make sense of raw data. Parsing is common to almost all computer systems: It is involved every time sequential data is read and elaborated into structured data. The theory of parsing usually focuses ...

EPFL2021

Gramatron: Effective Grammar-Aware Fuzzing

Mathias Josef Payer

Fuzzers aware of the input grammar can explore deeper program states using grammar-aware mutations. Existing grammar-aware fuzzers are ineffective at synthesizing complex bug triggers due to: (i) grammars introducing a sampling bias during input generation ...

ASSOC COMPUTING MACHINERY2021

Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement

James Henderson, Alireza Mohammadshahi

We propose the Recursive Non-autoregressive Graph-to-graph Transformer architecture (RNG-Tr) for the iterative refinement of arbitrary graphs through the recursive application of a non-autoregressive Graph-to-Graph Transformer and apply it to syntactic dep ...

2021

Zippy LL(1) Parsing with Derivatives

Viktor Kuncak, Romain Edelmann, Jad Hamza

In this paper, we present an efficient, functional, and formally verified parsing algorithm for LL(1) context-free expressions based on the concept of derivatives of formal languages. Parsing with derivatives is an elegant parsing technique, which, in the ...

ASSOC COMPUTING MACHINERY2020

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

Annotated References in the Historiography on Venice: 19th–21st centuries

Giovanni Colavizza, Matteo Romanello

We publish a dataset containing more than 40’000 manually annotated references from a broad corpus of books and journal articles on the history of Venice. References were considered from both reference lists and footnotes, include primary and secondary sou ...

2017

LMS-Verify: Abstraction without Regret for Verified Systems Programming’

Nada Amin, Tiark Rompf

Performance critical software is almost always developed in C, as programmers do not trust high-level languages to deliver the same reliable performance. This is bad because low-level code in unsafe languages attracts security vulnerabilities and because d ...

Assoc Computing Machinery2017

A pilot study on eliciting human operations decision in purchasing and measuring their impact on supply chain efficiency

Rémy Glardon, Souleïman Naciri, Min-Jung Yoo, Yvonne Badulescu

This paper presents a methodology for eliciting the behavioural model of purchasers' decision-making in a supply chain environment. The objective of the work is to explicitly describe the relationship between a human user's behaviour and the resulting perf ...

Pergamon-Elsevier Science Ltd2017

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Specialising Parsers for Queries

Manohar Jonnalagedda

Many software systems consist of data processing components that analyse large datasets to gather information and learn from these. Often, only part of the data is relevant for analysis. Data processing systems contain an initial preprocessing step that fi ...

EPFL2016

Word Sequence Modeling using Deep Learning : an End-to-end Approach and its Applications

Joël Yvon Roland Legrand

For a long time, natural language processing (NLP) has relied on generative models with task specific and manually engineered features. Recently, there has been a resurgence of interest for neural networks in the machine learning community, obtaining state ...

EPFL2016

Automating Grammar Comparison

Viktor Kuncak, Mikaël Mayer, Ravichandhran Kandhadai Madhavan

We consider from a practical perspective the problem of checking equivalence of context-free grammars. We present techniques for proving equivalence, as well as techniques for finding counter-examples that establish non-equivalence. Among the key building ...

2015

Staged parser combinators for efficient data processing

Martin Odersky, Sandro Stucki, Thierry Coppey, Manohar Jonnalagedda, Tiark Rompf

Parsers are ubiquitous in computing, and many applications depend on their performance for decoding data efficiently. Parser combinators are an intuitive tool for writing parsers: tight integration with the host language enables grammar specifications to b ...

ACM Press2014