Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Learning Deterministic Finite Automata from Interleaved Strings
verfasst von : Joshua Jones, Tim Oates
Erschienen in: Grammatical Inference: Theoretical Results and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Workflows are an important knowledge representation used to understand and automate processes in diverse task domains. Past work has explored the problem of learning workflows from traces of processing. In this paper, we are concerned with learning workflows from
interleaved
traces captured during the concurrent processing of multiple task instances. We first present an abstraction of the problem of recovering workflows from interleaved example traces in terms of grammar induction. We then describe a two-stage approach to reasoning about the problem, highlighting some negative results that demonstrate the need to work with a restricted class of languages. Finally, we give an example of a restricted language class called
terminated languages
for which an accepting deterministic finite automaton (DFA) can be recovered in the limit from interleaved strings, and make remarks about the applicability of the two-stage approach to terminated languages.