2022/06/28 by Markus L. Schmid, Schmid, Markus L.
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Data Quality and Management #Databases (cs.DB) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2206.13918
openalex publication_date 2022/06/28 · openalex created_date 2022/07/01 · openalex updated_date 2026/07/28
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.