In this paper we give the cost, in terms of states, of some basic operations (union, intersection, concatenation, and Kleene star) on regular languages in the unary case (where the alphabet contains only one symbol). These costs are given by explicitly determining the number of states in the noncyclic and cyclic parts of the resulting automata. Furthermore, we prove that our bounds are optimal. We also present an interesting connection to Jacobsthal's function from number theory.

Unary Language Operations, State Complexity and Jacobsthal's Function / G. Pighizzini, J. Shallit. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 13:1(2002), pp. 145-159. [10.1142/S012905410200100X]

Unary Language Operations, State Complexity and Jacobsthal's Function

G. Pighizzini
Primo
;
2002

Abstract

In this paper we give the cost, in terms of states, of some basic operations (union, intersection, concatenation, and Kleene star) on regular languages in the unary case (where the alphabet contains only one symbol). These costs are given by explicitly determining the number of states in the noncyclic and cyclic parts of the resulting automata. Furthermore, we prove that our bounds are optimal. We also present an interesting connection to Jacobsthal's function from number theory.
Finite automata; formal languages; number theory; state complexity; unary languages
Settore INF/01 - Informatica
2002
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/2434/35127
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 115
  • ???jsp.display-item.citation.isi??? ND
social impact