5 papers
The Stochastic Target Discounted-Sum Problem
Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran +2
The target discounted-sum problem (TDS) asks, given a finite integer alphabet , a rational discount factor , and a rational target , whether some infinite sequence over $Σ…
Categorizer Automata for Discounted-Sum Payoffs
Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran +2
Categorizing continuous data into discrete bins is a fundamental operation in artificial intelligence. We introduce the categorizer automaton, a deterministic automaton that reads…
An Empirical Comparison of General Context-Free Parsers
Huan Vo, Danushka Liyanage, Hong Jin Kang +2
Parsing underpins a vast range of software engineering tasks, from compilers and static analyzers to language servers and fuzz testing tools. Yet most parsers deployed in practice…
Example-Free Learning of Regular Languages with Prefix Queries
Eve Fernando, Sasha Rubin, Rahul Gopinath
Language learning refers to the problem of inferring a mathematical model which accurately represents a formal language. Many language learning algorithms learn by asking certain t…
Reusable Formal Verification of DAG-based Consensus Protocols
Nathalie Bertrand, Pranav Ghorpade, Sasha Rubin +2
Blockchains use consensus protocols to reach agreement, e.g., on the ordering of transactions. DAG-based consensus protocols are increasingly adopted by blockchain companies to red…