Paper Info
Title
Learning deterministic finite automata from interleaved strings
Abstract
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.
Year
DOI
Venue
2010
10.1007/978-3-642-15488-1_8
ICGI
Keywords
Field
DocType
diverse task domain,two-stage approach,deterministic finite automaton,restricted language class,restricted class,multiple task instance,past work,interleaved example trace,concurrent processing,interleaved trace,interleaved string,grammar induction,deterministic finite automata,knowledge representation,language learning,regular language
Programming language,Computer science,Theoretical computer science,Artificial intelligence,Regular language,Two-way deterministic finite automaton,Knowledge representation and reasoning,Nondeterministic finite automaton,Deterministic automaton,Nested word,Deterministic finite automaton,Deterministic pushdown automaton,Machine learning
Conference
Volume
ISSN
ISBN
6339
0302-9743
3-642-15487-5
Citations 
PageRank 
References 
1
0.34
8
Authors
2
Name
Order
Citations
PageRank
Joshua Jones1889.93
Tim Oates21069190.77