BK
B. Kollmann
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
1 records found
1
The goal of DFA learning is to infer a target DFA from a set of positive and negative observations. Active learning methods allow a learner to hypothesize about the target DFA by querying a teacher. Constructing a teacher that can efficiently answer these queries can significantly speed up the learning process. A distinguish query allows the learner to provide two words for the teacher and the teacher responds with a distinguishing suffix (i.e. a suffix such that if it is concatenated to the two provided words, one of the newly formed words will be among the positive observations, and the other among the negatives).
In this thesis, our aim is to design different implementations of a data structure that supports distinguish queries (DistinguishQueryDataStructure), and compare them through theoretical and experimental analysis.
To this end, we introduce the double trie, and show that using this data structure, it is possible to reduce distinguish queries to set intersection queries.
Then we design three different implementations of DistinguishQueryDataStructure, one of which uses a trie based approach with depth-first search, and two of which are based on the double trie.
Our experimental analysis shows that a double trie-based method can compete with, and even outperform in some cases the trie and depth-first-search-based approach. ...
In this thesis, our aim is to design different implementations of a data structure that supports distinguish queries (DistinguishQueryDataStructure), and compare them through theoretical and experimental analysis.
To this end, we introduce the double trie, and show that using this data structure, it is possible to reduce distinguish queries to set intersection queries.
Then we design three different implementations of DistinguishQueryDataStructure, one of which uses a trie based approach with depth-first search, and two of which are based on the double trie.
Our experimental analysis shows that a double trie-based method can compete with, and even outperform in some cases the trie and depth-first-search-based approach. ...
The goal of DFA learning is to infer a target DFA from a set of positive and negative observations. Active learning methods allow a learner to hypothesize about the target DFA by querying a teacher. Constructing a teacher that can efficiently answer these queries can significantly speed up the learning process. A distinguish query allows the learner to provide two words for the teacher and the teacher responds with a distinguishing suffix (i.e. a suffix such that if it is concatenated to the two provided words, one of the newly formed words will be among the positive observations, and the other among the negatives).
In this thesis, our aim is to design different implementations of a data structure that supports distinguish queries (DistinguishQueryDataStructure), and compare them through theoretical and experimental analysis.
To this end, we introduce the double trie, and show that using this data structure, it is possible to reduce distinguish queries to set intersection queries.
Then we design three different implementations of DistinguishQueryDataStructure, one of which uses a trie based approach with depth-first search, and two of which are based on the double trie.
Our experimental analysis shows that a double trie-based method can compete with, and even outperform in some cases the trie and depth-first-search-based approach.
In this thesis, our aim is to design different implementations of a data structure that supports distinguish queries (DistinguishQueryDataStructure), and compare them through theoretical and experimental analysis.
To this end, we introduce the double trie, and show that using this data structure, it is possible to reduce distinguish queries to set intersection queries.
Then we design three different implementations of DistinguishQueryDataStructure, one of which uses a trie based approach with depth-first search, and two of which are based on the double trie.
Our experimental analysis shows that a double trie-based method can compete with, and even outperform in some cases the trie and depth-first-search-based approach.