The paper focuses on deterministic and unambiguous finite automata (DFA's and UNFA's respectively for short) in the case of a one-letter alphabet.We present a structural characterization of unary UNFA's and some considerations relating minimal UNFA's with minimum DFA's recognizing a given unary language. We also present an algorithm for the construction of a minimal UNFA for a unary regular language.Then we establish a correspondence between pairs of UNFA's recognizing a unary language and its complement respectively, and the disjoint covering systems of number theory. It allows us to provide some conditions relating the number of successful simple pathsand the lengths of cycles in an UNFA recognizing a unary language with the same parameters in an UNFA recognizing its complement.
Some Results on the Structure of Unary Unambiguous Automata
MADONIA M
2011-01-01
Abstract
The paper focuses on deterministic and unambiguous finite automata (DFA's and UNFA's respectively for short) in the case of a one-letter alphabet.We present a structural characterization of unary UNFA's and some considerations relating minimal UNFA's with minimum DFA's recognizing a given unary language. We also present an algorithm for the construction of a minimal UNFA for a unary regular language.Then we establish a correspondence between pairs of UNFA's recognizing a unary language and its complement respectively, and the disjoint covering systems of number theory. It allows us to provide some conditions relating the number of successful simple pathsand the lengths of cycles in an UNFA recognizing a unary language with the same parameters in an UNFA recognizing its complement.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.