Skip to main navigation Skip to search Skip to main content

Games for Succinctness of Regular Expressions

  • Miikka Vilander

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

10 Downloads (Pure)

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 languageEnglish
Title of host publication12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2021)
PublisherOpen Publishing Association
Pages258–272
Number of pages15
Volume346
DOIs
Publication statusPublished - 17 Sept 2021
Publication typeA4 Article in conference proceedings
EventInternational 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

NameElectronic Proceedings in Theoretical Computer Science
PublisherOpen Publishing Association
ISSN (Electronic)2075-2180

Conference

ConferenceInternational Symposium on Games, Automata, Logics, and Formal Verification
Abbreviated titleGandALF 2021
Period20/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