Concept

Pumping lemma for context-free languages

Related publications (7)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Zippy LL(1) Parsing with Derivatives

Viktor Kuncak, Jad Hamza, Romain Edelmann

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

IRGC Guidelines for the Governance of Systemic Risks

Marie-Valentine Renée Agnès Florin, Anjali Devi Vanapilli Nursimulu

IRGC’s guidelines for the governance of systemic risks addresses the question of how to deal with systemic risks in the context of system transitions, i.e., in situations that require adaptation to new context conditions or transformation of an organisatio ...

International Risk Governance Center (IRGC)2018

Proactive Synthesis of Recursive Tree-to-String Functions from Examples

Viktor Kuncak, Mikaël Mayer, Jad Hamza

Synthesis from examples enables non-expert users to generate programs by specifying examples of their behavior. A domain-specific form of such synthesis has been recently deployed in a widely used spreadsheet software product. In this paper we contribute t ...

2017

Type Soundness for Dependent Object Types (DOT)

Tiark Rompf, Nada Amin

Scala's type system unifies aspects of ML modules, object-oriented, and functional programming. The Dependent Object Types (DOT) family of calculi has been proposed as a new theoretic foundation for Scala and similar expressive languages. Unfortunately, ty ...

Assoc Computing Machinery2016

Type Soundness for Dependent Object Types’

Tiark Rompf, Nada Amin

Scala’s type system unifies aspects of ML modules, object-oriented, and functional programming. The Dependent Object Types (DOT) family of calculi has been proposed as a new theoretic foundation for Scala and similar expressive languages. Unfortunately, ty ...

2016

Pattern-wise trust assessment of sensor data

Karl Aberer, Mehdi Riahi, Robert Gwadera

One of the most important tasks of a sensor network (SN) is to detect occurrences of interesting events in the monitored environment. However, data measured by SN is often affected by errors. We investigate the problem of assessing trustworthiness (trust) ...

2014

Efficient String Matching Algorithms for Combinatorial Universal Denoising

Suhas Diggavi, Sanket Dusad

Inspired by the combinatorial denoising method {\tt DUDE} \cite{WOSVW04}, we present efficient algorithms for implementing this idea for arbitrary contexts or for using it within subsequences. We also propose effective, efficient denoising error estimators ...

2005