Games for Succinctness of Regular Expressions

Miikka Vilander
(Computing Sciences, Tampere University, Finland)

We present a version of so called formula size games for regular expressions. These games characterize the equivalence of languages up to expressions of a given size. We use the regular expression size game to give a simple proof of a known non-elementary succinctness gap between first-order logic and regular expressions. We also use the game to only count the number of stars in an expression instead of the overall size. For regular expressions this measure trivially gives a hierarchy in terms of expressive power. We obtain such a hierarchy also for what we call RE over star-free expressions, where star-free expressions, that is ones with complement but no stars, are combined using the operations of regular expressions.

In Pierre Ganty and Davide Bresolin: Proceedings 12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2021), Padua, Italy, 20-22 September 2021, Electronic Proceedings in Theoretical Computer Science 346, pp. 258–272.
Published: 17th September 2021.

ArXived at: http://dx.doi.org/10.4204/EPTCS.346.17 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org