Classifying regular languages by a split game

DOI10.1016/j.tcs.2006.12.041zbMath1162.91327OpenAlexW2070107228MaRDI QIDQ1022599

Qiqi Yan

Publication date: 22 June 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.12.041

zbMATH Keywords

regular expressionstar heightEF-gameomega powersplit game

Mathematics Subject Classification ID

Applications of game theory (91A80) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monadic partition logics and finite automata
• First-order logic and star-free sets
• Algorithms for determining relative star height and star height
• Remark on the star-height-problem
• Classifying regular events in symbolic logic
• More languages of generalised star height 1
• Some results on the generalized star-height problem
• The dot-depth hierarchy of star-free languages is infinite
• Reasoning about infinite computations
• Transition graphs and the star-height of regular events
• Dot-depth of star-free events
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• On finite monoids having only trivial subgroups

This page was built for publication: Classifying regular languages by a split game