SPLASH 2020
Sun 15 - Sat 21 November 2020 Online Conference
Tue 17 Nov 2020 16:00 - 16:20 at SPLASH-I - T-5 Chair(s): Tyler Sorensen, Raffi Khatchadourian
Wed 18 Nov 2020 04:00 - 04:20 at SPLASH-I - T-5 Chair(s): Burcu Kulahcioglu Ozkan, Reuben Rowe

We propose a solution to the problem of efficient matching regular expressions (regexes) with bounded repetition, such as $\texttt{(ab){1,100}}$, using deterministic automata. For this, we introduce novel \emph{counting-set automata (CsAs)}, automata with registers that can hold sets of bounded integers and can be manipulated by a limited portfolio of constant-time operations. We present an algorithm that compiles a large sub-class of regexes to deterministic CsAs. This includes (1) a novel Antimirov-style translation of regexes with counting to \emph{counting automata (CAs)}, nondeterministic automata with bounded counters, and (2) our main technical contribution, a determinization of CAs that outputs CsAs. The main advantage of this workflow is that \emph{the size of the produced CsAs does not depend on the repetition bounds used in the regex} (while the size of the DFA is exponential to them). Our experimental results confirm that deterministic CsAs produced from practical regexes with repetition are indeed vastly smaller than the corresponding DFAs. More importantly, our prototype matcher based on CsA simulation handles practical regexes with repetition regardless of sizes of counter bounds. It easily copes with regexes with repetition where state-of-the-art matchers struggle.

Tue 17 Nov

Displayed time zone: Central Time (US & Canada) change

15:00 - 16:20
T-5OOPSLA at SPLASH-I +12h
Chair(s): Tyler Sorensen University of California at Santa Cruz, Raffi Khatchadourian City University of New York
15:00
20m
Talk
Actor Concurrency Bugs: A Comprehensive Study on Symptoms, Root Causes, API Usages, and Differences
OOPSLA
Mehdi Bagherzadeh Oakland University, Nicholas Fireman Oakland University, Anas Shawesh Oakland University, Raffi Khatchadourian City University of New York
Link to publication DOI Pre-print Media Attached
15:20
20m
Talk
Knowing When to Ask: Sound Scheduling of Name Resolution in Type Checkers Derived from Declarative Specifications
OOPSLA
Arjen Rouvoet Delft University of Technology, Hendrik van Antwerpen Delft University of Technology, Casper Bach Poulsen Delft University of Technology, Robbert Krebbers Radboud University Nijmegen, Eelco Visser Delft University of Technology
Link to publication DOI Pre-print Media Attached
15:40
20m
Talk
Fuzzing Channel-Based Concurrency Runtimes using Types and Effects
OOPSLA
Quentin Stiévenart Vrije Universiteit Brussel, Magnus Madsen Aarhus University
Link to publication DOI Media Attached
16:00
20m
Talk
Regex Matching with Counting-Set Automata
OOPSLA
Lenka Turoňová Brno University of Technology, Lukáš Holík Brno University of Technology, Ondřej Lengál Brno University of Technology, Olli Saarikivi Microsoft, Margus Veanes Microsoft, Tomáš Vojnar Brno University of Technology
Link to publication DOI Media Attached

Wed 18 Nov

Displayed time zone: Central Time (US & Canada) change

03:00 - 04:20
T-5OOPSLA at SPLASH-I
Chair(s): Burcu Kulahcioglu Ozkan MPI-SWS, Reuben Rowe University College London
03:00
20m
Talk
Actor Concurrency Bugs: A Comprehensive Study on Symptoms, Root Causes, API Usages, and Differences
OOPSLA
Mehdi Bagherzadeh Oakland University, Nicholas Fireman Oakland University, Anas Shawesh Oakland University, Raffi Khatchadourian City University of New York
Link to publication DOI Pre-print Media Attached
03:20
20m
Talk
Knowing When to Ask: Sound Scheduling of Name Resolution in Type Checkers Derived from Declarative Specifications
OOPSLA
Arjen Rouvoet Delft University of Technology, Hendrik van Antwerpen Delft University of Technology, Casper Bach Poulsen Delft University of Technology, Robbert Krebbers Radboud University Nijmegen, Eelco Visser Delft University of Technology
Link to publication DOI Pre-print Media Attached
03:40
20m
Talk
Fuzzing Channel-Based Concurrency Runtimes using Types and Effects
OOPSLA
Quentin Stiévenart Vrije Universiteit Brussel, Magnus Madsen Aarhus University
Link to publication DOI Media Attached
04:00
20m
Talk
Regex Matching with Counting-Set Automata
OOPSLA
Lenka Turoňová Brno University of Technology, Lukáš Holík Brno University of Technology, Ondřej Lengál Brno University of Technology, Olli Saarikivi Microsoft, Margus Veanes Microsoft, Tomáš Vojnar Brno University of Technology
Link to publication DOI Media Attached