Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | 12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2021) |
| Publisher | Open Publishing Association |
| Pages | 258–272 |
| Number of pages | 15 |
| Volume | 346 |
| DOIs | |
| Publication status | Published - 17 Sept 2021 |
| Publication type | A4 Article in conference proceedings |
| Event | International Symposium on Games, Automata, Logics, and Formal Verification - Duration: 20 Sept 2021 → 22 Sept 2021 Conference number: 12 https://gandalf2021.math.unipd.it/ |
Publication series
| Name | Electronic Proceedings in Theoretical Computer Science |
|---|---|
| Publisher | Open Publishing Association |
| ISSN (Electronic) | 2075-2180 |
Conference
| Conference | International Symposium on Games, Automata, Logics, and Formal Verification |
|---|---|
| Abbreviated title | GandALF 2021 |
| Period | 20/09/21 → 22/09/21 |
| Internet address |
Keywords
- succinctness
- formula size game
- Regular expression
Publication forum classification
- Publication forum level 0
Fingerprint
Dive into the research topics of 'Games for Succinctness of Regular Expressions'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver