Some Algebraic Structures Arising from Black-box Automata
Jānis Cı̄rulis · Baltic Journal of Modern Computing · 2021
A representative example of a black-box automaton is provided by a (possibly nondeterministic) automaton with any information about its states ignored.Such an automaton realizes a certain many-valued transformation ϕ of input strings available to it into output strings.The outcome space of a black-box automaton is defined to be the set of all pairs (α, γ) where α is its input string, and γ ∈ ϕ(α) is any of the corresponding output strings.We show that each outcome space carries a structure of a tree-ordered poset equipped with two special binary relations and that there is, up to isomorphisms, a bijective correspondence between such relational structures and the so called exact black-box automata.Moreover, an otcome space is also a bisemigroup of certain kind.Virtual states of a black-box automaton also are discussed.