No label defined (Q3984633)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 26439
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 26439 |
Statements
27 June 1992
0 references
congruences of automata
0 references
indistinguishable state pairs
0 references
Three types of indistinguishable state pairs \((a,b)\) in a Moore automaton were defined by \textit{A. Ádám} and \textit{I. Babcsányi} [Stud. Sci. Math. ( Zbl 0724.68057)(to appear)] depending on the properties of the input words \(p\) satisfying \(\delta(a,p)=\delta(b,p)\). Theorem 1 of the present paper answers the following problem: If \(I\) is a subset of \(\{1,2,3\}\) and \(m(\geq 2)\) is an integer, what is the minimum of states of the automata \({\mathcal A}=(A,X,Y,\delta,\lambda)\) such that (1) \({\mathcal A}\) has an indistinguishable state pair of type \(i\) exactly if \(i\in I\) and (2) the number of output signs occurring actually in \({\mathcal A}\) equals \(m\). Theorem 2 states that the partition of \(A\) induced by the output function \(\lambda\) is a congruence if \({\mathcal A}\) is an automaton for which minimum holds in Theorem 1. In the last section a special type of congruences (assigned to state pairs) is studied.
0 references