Subsequence versus substring constraints in sequence pattern languages

DOI10.1007/S00236-019-00347-5OpenAlexW2984588951MaRDI QIDQ2022305FDOQ2022305

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

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)