Back to Search
Start Over
Games for Succinctness of Regular Expressions
- Source :
- Electronic Proceedings in Theoretical Computer Science. 346:258-272
- Publication Year :
- 2021
- Publisher :
- Open Publishing Association, 2021.
-
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.<br />In Proceedings GandALF 2021, arXiv:2109.07798
- Subjects :
- FOS: Computer and information sciences
Discrete mathematics
Computer Science - Logic in Computer Science
Hierarchy (mathematics)
113 Computer and information sciences
Measure (mathematics)
Expression (mathematics)
Logic in Computer Science (cs.LO)
Succinctness
Simple (abstract algebra)
111 Mathematics
Regular expression
Equivalence (measure theory)
Mathematics
Complement (set theory)
Subjects
Details
- ISSN :
- 20752180
- Volume :
- 346
- Database :
- OpenAIRE
- Journal :
- Electronic Proceedings in Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....c318c5da50920d87955a7a73285911c3