Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/30404
Title: | Subsequence versus substring constraints in sequence pattern languages | Authors: | ENGELS, Steven TAN, Tony VAN DEN BUSSCHE, Jan |
Issue Date: | 2021 | Publisher: | SPRINGER | Source: | ACTA INFORMATICA, 58, p. 35-56 | Abstract: | A family of logics for expressing patterns in sequences is investigated. The logics are all fragments of first-order logic, but they are variable-free. Instead, they can use substring and subsequence constraints as basic propositions. Propositions expressing constraints on the beginning or the end of the sequence are also available. Also wildcards can be used, which is important when the alphabet is not fixed, as is typical in database applications. The maximal logic with all four features of substring, subsequence, begin-end constraints, and wildcards, turns out to be equivalent to the family of star-free regular languages of dot-depth at most one. We investigate the lattice formed by taking all possible combinations of the above four features, and show it to be strict. For instance, we formally confirm what might intuitively be expected, namely, that boolean combinations of substring constraints are not sufficient to express subsequence constraints, and vice versa. We show an expressiveness hierarchy results from allowing multiple wildcards. We also investigate what happens with regular expressions when concatenation is replaced by subsequencing. Finally, we study the expressiveness of our logic relative to first-order logic. | Notes: | Tan, T (reprint author), Natl Taiwan Univ, Taipei, Taiwan. steven.engels@uhasselt.be; tonytan@csie.ntu.edu.tw; jan.vandenbussche@uhasselt.be |
Other: | Tan, T (reprint author), Natl Taiwan Univ, Taipei, Taiwan. steven.engels@uhasselt.be; tonytan@csie.ntu.edu.tw; jan.vandenbussche@uhasselt.be | Document URI: | http://hdl.handle.net/1942/30404 | ISSN: | 0001-5903 | e-ISSN: | 1432-0525 | DOI: | 10.1007/s00236-019-00347-5 | ISI #: | WOS:000494792800002 | Rights: | 2019 Springer Nature Switzerland AG. Part of Springer Nature. | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2020 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
pattern-ACIN-v4.pdf | Peer-reviewed author version | 379.9 kB | Adobe PDF | View/Open |
Engels2021_Article_SubsequenceVersusSubstringCons.pdf Restricted Access | Published version | 380.98 kB | Adobe PDF | View/Open Request a copy |
Page view(s)
60
checked on Sep 7, 2022
Download(s)
30
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.