UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
Top Cited Papers
- 1 February 2002
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 13 (1), 145-159
- https://doi.org/10.1142/s012905410200100x
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.Keywords
This publication has 8 references indexed in Scilit:
- On a question of regarding visibility of lattice pointsMathematika, 1996
- The state complexities of some basic operations on regular languagesTheoretical Computer Science, 1994
- On the state complexity of intersection of regular languagesACM SIGACT News, 1991
- Finite automata and unary languagesTheoretical Computer Science, 1986
- ESTIMATION OF THE TSCHEBYSCHEV THETA-FUNCTION OF THE KTH PRIME NUMBER AND HIGH VALUES OF THE OMEGA(N)-NUMBER FUNCTION OF PRIME N-DIVISORSActa Arithmetica, 1982
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite AutomataIEEE Transactions on Computers, 1971
- Über eine zahlentheoretische Funktion von JacobsthalMathematische Annalen, 1967
- On a Problem of PartitionsAmerican Journal of Mathematics, 1942