Extending Shinohara's Algorithm for Computing Descriptive (Angluin-Style) Patterns to Subsequence Patterns
share
The introduction of pattern languages in the seminal work [Angluin, “Finding Patterns Common to a Set of Strings”, JCSS 1980] has revived the classical model of inductive inference (learning in the limit, gold-style learning). In [Shinohara, “Polynomial Time Inference of Pattern Languages and Its Application”, 7th IBM Symposium on Mathematical Foundations of Computer Science 1982] a simple and elegant algorithm has been introduced that, based on membership queries, computes a pattern that is descriptive for a given sample of input strings (and, consequently, can be employed in strategies for inductive inference). In this paper, we give a brief survey of the recent work [Kleest-Meißner et al., “Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints”, ICDT 2022], where the classical concepts of Angluin-style (descriptive) patterns and the respective Shinohara's algorithm are extended to a query class with applications in complex event recognition – a modern topic from databases.
READ FULL TEXT