Paper Info
Title
Exploring the Relationship between the Structural and the Actual Similarities of Automata
Abstract
One of the most common representations of formal languages is deterministic finite-state automata. In recent years, a bunch of papers dedicated to the problem of synthesizing such an automaton by a list of positive and negative examples of some formal language was published. Many of proposed models try to construct candidate automaton, which is believed to somehow approximate the target one. In this paper, we exploring the relationship between the structural similarity of candidate and target finite-state automata and the percentage of common words in their formal languages. We formalize two different notions of automata similarity, and present the results of their comparison and draw conclusions regarding the applicability of these definitions to the problem of grammar inference.
Year
DOI
Venue
2019
10.1145/3310986.3311032
Proceedings of the 3rd International Conference on Machine Learning and Soft Computing
Keywords
DocType
ISBN
deterministic finite automaton, formal language, grammar inference
Conference
978-1-4503-6612-0
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Petr Grachev100.68
Roman Bezborodov200.34
Ivan Smetannikov301.35
Andrey Filchenkov44615.80