Search

• < Previous
• 1
• Next >

---

Efficient reduction of nondeterministic automata with application to language inclusion testing

Lorenzo Clemente ; Richard Mayr.

We present efficient algorithms to reduce the size of nondeterministic B\"uchi word automata (NBA) and nondeterministic finite word automata (NFA), while retaining their languages. Additionally, we describe methods to solve PSPACE-complete automata problems like language universality, equivalence,&nbsp;[&hellip;]

---

Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs

Richard Mayr ; Eric Munday.

We study countably infinite Markov decision processes (MDPs) with real-valued transition rewards. Every infinite run induces the following sequences of payoffs: 1. Point payoff (the sequence of directly seen transition rewards), 2. Mean payoff (the sequence of the sums of all rewards so far, divided&nbsp;[&hellip;]

---