Star height via games

DOI10.1109/LICS.2015.29MaRDI QIDQ4635805zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(5)

• Concatenation hierarchies: new bottle, old wine
• The boundedness and zero isolation problems for weighted automata over nonnegative rationals
• Regular expression length via arithmetic formula complexity
• Generic results for concatenation hierarchies
• scientific article; zbMATH DE number 7379291 (Why is no real title available?)

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)