Loading...
Fundamental results for learning deterministic extended finite state machines from queries
Ipate, F. Gheorghe, Marian Lefticaru, Raluca
Ipate, F.
Gheorghe, Marian
Lefticaru, Raluca
Publication Date
2021-03-16
End of Embargo
Supervisor
Rights
© 2021 Elsevier. Reproduced in accordance with the publisher's self-archiving policy. This manuscript version is made available under the CC-BY-NC-ND 4.0 license (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Peer-Reviewed
Yes
Open Access status
Accepted for publication
2020-09-14
Institution
Department
Awarded
Embargo end date
Additional title
Abstract
Regular language inference, initiated by Angluin, has many developments, including applications in software engineering and testing. However, the capability of finite automata to model the system data is quite limited and, in many cases, extended finite state machine formalisms, that combine the system control with data structures, are used instead. The application of Angluin-style inference algorithms to extended state machines would involve constructing a minimal deterministic extended finite state machine consistent with a deterministic 3-valued deterministic finite automaton. In addition to the usual, accepting and rejecting, states of finite automaton, a 3-valued deterministic finite automaton may have “don't care” states; the sequences of inputs that reach such states may be considered as accepted or rejected, as is convenient. The aforementioned construction reduces to finding a minimal deterministic finite automaton consistent with a 3-valued deterministic finite automaton, that preserves the deterministic nature of the extended model that also handles the data structure associated with it. This paper investigates fundamental properties of extended finite state machines in relation to Angluin's language inference problem and provides an inference algorithm for such models.
Version
Accepted manuscript
Citation
Ipate F, Gheorghe M and Lefticaru R (2021) Fundamental results for learning deterministic extended finite state machines from queries. Theoretical Computer Science. 862: 160-173.
Link to publisher’s version
Link to published version
Link to Version of Record
Type
Article