Subsequence versus substring constraints in sequence pattern languages

DOI10.1007/S00236-019-00347-5MaRDI QIDQ2022305zbMATH OpenOpenAlexFDO

Authors Steven Engels, Tony Tan, Jan Van den Bussche

Publication date 28 April 2021

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-019-00347-5

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Forest Expressions
• Constrained expressions and their derivatives
• Definable relations and first-order query languages over strings
• Decidability in the logic of subsequences and supersequences
• Graph logics with rational relations: the role of word combinatorics

Cites work

• scientific article; zbMATH DE number 4049066 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Automata and Logics for Words and Trees over an Infinite Alphabet
• Closure under reversal of languages over infinite alphabets
• Dot-depth of star-free events
• Finite state machines for strings over infinite alphabets
• Graph reachability and pebble automata over infinite alphabets
• On pebble automata for data languages with decidable emptiness problem
• On separation by locally testable and locally threshold testable languages
• Regular expressions for languages over infinite alphabets
• Sequence data mining. Forward by Professor Jiawei Han
• The dot-depth hierarchy of star-free languages is infinite
• The dot-depth hierarchy, 45 years later
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(3)

• Combined super-/substring and super-/subsequence problems
• Solving Not-Substring Constraint withFlat Abstraction
• Generalized pattern matching and periodicity under substring consistent equivalence relations

This page was built for publication: Subsequence versus substring constraints in sequence pattern languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022305)