Learning Pairwise Disjoint Simple Languages from Positive Examples

2017/06/06 by Alexis Linard, Linard, Alexis, Rick Smetsers +9
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning (cs.LG) #Machine Learning and Algorithms #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1706.01663

openalex publication_date 2017/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A classical problem in grammatical inference is to identify a deterministic finite automaton (DFA) from a set of positive and negative examples. In this paper, we address the related - yet seemingly novel - problem of identifying a set of DFAs from examples that belong to different unknown simple regular languages. We propose two methods based on compression for clustering the observed positive examples. We apply our methods to a set of print jobs submitted to large industrial printers.

Related

• Learning Several Languages from Labeled Strings: State Merging and Evolutionary Approaches
• Learning DFAs from Positive Examples Only via Word Counting
• Learning from Positive and Negative Examples: New Proof for Binary Alphabets
• DFAMiner: Mining minimal separating DFAs from labelled samples
• Learning Deterministic Finite Automata Decompositions from Examples and Demonstrations