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.
2011
Finite Automata ; Ambiguity; Unary alphabet.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/8653
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact