Constrained Multi-Tildes: Derived Term and Position Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929218452979712 |
|---|---|
| author | Attou, Samira Mignot, Ludovic Miklarz, Clément Nicart, Florent |
| author_facet | Attou, Samira Mignot, Ludovic Miklarz, Clément Nicart, Florent |
| contents | Multi-tildes are regular operators that were introduced to enhance the factorization power of regular expressions, allowing us to add the empty word in several factors of a catenation product of languages. In addition to multi-bars, which dually remove the empty word, they allow representing any acyclic automaton by a linear-sized expression, whereas the lower bound is exponential in the classic case.
In this paper, we extend multi-tildes from disjunctive combinations to any Boolean combination, allowing us to exponentially enhance the factorization power of tildes expressions. Moreover, we show how to convert these expressions into finite automata and give a Haskell implementation of them using advanced techniques of functional programming. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12111 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constrained Multi-Tildes: Derived Term and Position Automata Attou, Samira Mignot, Ludovic Miklarz, Clément Nicart, Florent Formal Languages and Automata Theory Multi-tildes are regular operators that were introduced to enhance the factorization power of regular expressions, allowing us to add the empty word in several factors of a catenation product of languages. In addition to multi-bars, which dually remove the empty word, they allow representing any acyclic automaton by a linear-sized expression, whereas the lower bound is exponential in the classic case. In this paper, we extend multi-tildes from disjunctive combinations to any Boolean combination, allowing us to exponentially enhance the factorization power of tildes expressions. Moreover, we show how to convert these expressions into finite automata and give a Haskell implementation of them using advanced techniques of functional programming. |
| title | Constrained Multi-Tildes: Derived Term and Position Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2401.12111 |