History-Deterministic B\"uchi Automata are Succinct
classification
💻 cs.FL
keywords
automatonuchihistory-deterministicstatesactivelyautomatabeencombination
read the original abstract
We describe a history-deterministic B\"uchi automaton that has strictly less states than every language-equivalent deterministic B\"uchi automaton. This solves a problem that had been open since the introduction of history-determinism and actively investigated for over a decade. Our example automaton has 65 states, and proving its succinctness requires the combination of theoretical insights together with the aid of computers.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.