5 papers
Target Discounted Sum Problem on Markov Chains with Applications to Markov Decision Processes
Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran +2
The discounted sum is a way to aggregate a sequence of weights from a finite alphabet , i.e., for a discount factor , the discounted sum of a sequence ov…
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…