The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs

DOI10.1016/J.IPL.2017.07.001MaRDI QIDQ2398505zbMATH OpenOpenAlexFDO

Authors Hüsnü Yenigün, Nina Yevtushenko, Natalia Kushik

Publication date 16 August 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2017.07.001

zbMATH Keywords

formal methodsdeterministic finite state machinesadaptive sequencessynchronizing experiments

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The synchronization problem in protocol testing and its complexity
• On the complexity of existence of homing sequences for nondeterministic finite state machines
• Adaptive Testing of a Deterministic Implementation Against a Nondeterministic Finite State Machine
• Describing homing and distinguishing sequences for nondeterministic finite state machines via synchronizing automata
• The relation between preset distinguishing sequences and synchronizing sequences

Cites work

• scientific article; zbMATH DE number 3328721 (Why is no real title available?)
• Conformance Tests as Checking Experiments for Partial Nondeterministic FSM
• Least Upper Bounds on Minimal Terminal State Experiments for Two Classes of Sequential Machines
• Testing finite-state machines: state identification and verification

Cited in

(5)

• Adaptive experiments for state identification in finite state machines with timeouts
• On the complexity of existence of homing sequences for nondeterministic finite state machines
• The relation between preset distinguishing sequences and synchronizing sequences
• Introducing complexity to formal testing
• Deriving Homing Sequences for Finite State Machines with Timed Guards

This page was built for publication: The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2398505)