Show simple item record

dc.contributor.authorIpate, F.
dc.contributor.authorGheorghe, Marian
dc.contributor.authorLefticaru, Raluca
dc.date.accessioned2020-09-21T08:42:04Z
dc.date.accessioned2020-09-28T14:24:56Z
dc.date.available2020-09-21T08:42:04Z
dc.date.available2020-09-28T14:24:56Z
dc.date.issued2020
dc.identifier.citationIpate F, Gheorghe M and Lefticaru R (2020) Fundamental results for learning deterministic extended finite state machines from queries. Theoretical Computer Science. Accepted for publication.en_US
dc.identifier.urihttp://hdl.handle.net/10454/18046
dc.descriptionYesen_US
dc.description.abstractRegular 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.en_US
dc.language.isoenen_US
dc.relation.isreferencedbyhttps://doi.org/10.1016/j.tcs.2020.09.028en_US
dc.rights© 2020 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/)en_US
dc.subject3DFAen_US
dc.subjectFinite automataen_US
dc.subjectLearning from queriesen_US
dc.subjectExtended finite state machinesen_US
dc.subjectX-machinesen_US
dc.titleFundamental results for learning deterministic extended finite state machines from queriesen_US
dc.status.refereedYesen_US
dc.date.Accepted2020-09-14
dc.date.application2020-09-16
dc.typeArticleen_US
dc.date.EndofEmbargo2021-09-17
dc.type.versionAccepted manuscripten_US
dc.description.publicnotesThe full-text of this article will be released for public view at the end of the publisher embargo on 17 Sep 2021.en_US
dc.date.updated2020-09-21T07:42:15Z
refterms.dateFOA2020-09-28T14:25:21Z


Item file(s)

Thumbnail
Name:
learntcs07.pdf
Embargo:
2021-09-17
Size:
348.7Kb
Format:
PDF
Description:
ipate_et_al_2020

This item appears in the following Collection(s)

Show simple item record