Det har funnits stort intresse för testning från finita tillståndsmaskiner (FSM) som ett resultat av deras lämplighet för modellering eller specificering av statsbaserade system. Om det finns flera portar/interfaces används en FSM med flera portar och vid provning placeras en testare vid varje port. Om testarna inte kan kommunicera direkt med varandra och det inte finns någon global klocka så testar vi i den distribuerade testarkitekturen. Det är känt att användningen av den distribuerade testarkitekturen kan påverka testkraften och det senaste arbetet har karakteriserat detta i form av lokal ekvivalens: i den distribuerade testarkitekturen kan vi urskilja två FSM, såsom en implementering och en specifikation, om och endast om de inte är lokalt s-ekvivalenta. Det kan dock finnas många FSM som lokalt är likvärdiga med en given FSM och dessa FSM:s karaktär har inte undersökts. Detta dokument undersöker den uppsättning FSM som är lokalt S-ekvivalent med en given FSM M. Det visar att det finns en unik minsta FSM χ min (M ) och en unik största FSM χ max (M ) som är lokalt S-ekvivalent med M. Här minsta och största hänvisar till den uppsättning spår definieras av en FSM och därmed till dess semantik. Vi visar också att för en given FSM M den uppsättning FSM som är lokalt S-ekvivalent med M definierar en avgränsad lattice. Slutligen definierar vi en FSM som, bland alla FSM lokalt S-ekvivalent med M, har få stater. Vi ger alltså tre alternativa kanoniska FSM som är lokalt S-ekvivalenta med en FSM M: en som definierar den minsta uppsättningen spår, en som definierar den största uppsättningen spår, och en med få stater. Alla tre ger värdefull information och de två första kan produceras i tid som är polynom i termer av antalet stater av M. Vi visar att problemet med att hitta en s-ekvivalent FSM med få stater är NP-hård i allmänhet men kan lösas i polynom tid för specialfall där det finns två hamnar.
Det andra resultatet visar hur vi, med tanke på FSM M, kan definiera en partiell FSM x min ðM på ett sätt som modellerar M:s beteende när det ges kontrollerbara testfall REF.
Canonical Finite State Machines For Distributed Systems
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}