Star height via games

DOI10.1109/LICS.2015.29zbMATH Open1401.68148arXiv1708.03603OpenAlexW1495847632MaRDI QIDQ4635805FDOQ4635805

Authors: Mikołaj Bojańczyk 

Publication date: 23 April 2018

Published in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: This paper proposes a new algorithm deciding the star height problem. As shown by Kirsten, the star height problem reduces to a problem concerning automata with counters, called limitedness. The new contribution is a different algorithm for the limitedness problem, which reduces it to solving a Gale-Stewart game with an {omega}-regular winning condition.

Full work available at URL: https://arxiv.org/abs/1708.03603

Recommendations

• Distance desert automata and the star height problem
• Algorithms for determining relative inclusion star height and inclusion star height
• Foundations of Software Science and Computation Structures
• Algorithms for determining relative star height and star height
• Open problems about regular languages, 35 years later

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of game theory (91A80) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Cited In (5)

• Title not available (Why is that?)
• Regular expression length via arithmetic formula complexity
• Generic results for concatenation hierarchies
• The boundedness and zero isolation problems for weighted automata over nonnegative rationals
• Concatenation hierarchies: new bottle, old wine

This page was built for publication: Star height via games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635805)