On the Identification of a Finite Automaton by Its Input and Output Sequences in Case of Distortions

A method is proposed for checking whether a pair of observed distorted sequences can correspond to the true input and output sequences of a reference automaton, provided that the initial state of the automaton is unknown, and the proportion of deletions, insertions, and replacements of symbols is small. An example of applying the method for the case of a generalized shift register is given. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Authors
Melnikov S.Yu. , Samouylov K.E. , Zyazin A.V.
Conference proceedings
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher
Springer Science and Business Media Deutschland GmbH
Language
English
Pages
95-104
Status
Published
DOI
10.1007/978-3-031-50482-2_8
Volume
14123 LNCS
Year
2024
Organizations
  • 1 RUDN University, 6 Miklukho-Maklaya Street, Moscow, 117198, Russian Federation
  • 2 Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences (FRC CSC RAS), 44-2 Vavilov Street, Moscow, 119333, Russian Federation
  • 3 MIREA – Russian Technological University, 78 Vernadsky Avenue, Moscow, 119454, Russian Federation
Keywords
distorted sequence; finite state machine; random number generator
Cite
ГОСТ MLA RIS BibTex
Share

Other records