On NFAs where all states are final,initial, or both

We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversality and inequivalence problems for these NFAs. Next, we characterize the languages accepted. Finally, we discuss some state complexity problems involving such automata.     

State complexity of unique rational operations

For each basic language operation we define its “unique” counterpart as being the operation that results in a language whose words can be obtained uniquely through the given operation. These unique operations can arguably be viewed as combined basic operations, placing this work in the popular area of state complexity of combined operations on regular languages. We study the state complexity of unique rational operations and we provide upper bounds and empirical results meant to cast light into this matter. Equally important, we hope to have provided a generic methodology for estimating their state complexity.     

Detecting palindromes,patterns and borders in regular languages

Given a language L and a non-deterministic finite automaton M, we consider whether we can determine efficiently (in the size of M) if M accepts at least one word in L, or infinitely many words. Given that M accepts at least one word in L, we consider how long a shortest word can be. The languages L that we examine include the palindromes, the non-palindromes, the k-powers, the non-k-powers, the powers, the non-powers (also called primitive words), the words matching a general pattern, the bordered words, and the unbordered words.     

Number-theoretic functions which are equivalent to number of divisors

Let d(n) denote the number of positive integral divisors of n. In this paper we show that the Möbius function, μ(N), can be computed by a single call to an oracle for d(n). We also show that any function that depends solely on the exponents in the prime factorization of N can be computed by at most log₂ N calls to an oracle for d(N).     

Additive Number Theory via Automata Theory

Theory of Computing Systems - We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the...     

Efficient enumeration of words in regular languages

The cross-section enumeration problem is to list all words of length n$n$ in a regular language L$L$ in lexicographical order. The enumeration problem is to list the first m$m$ words in L$L$ according to radix order. We present an algorithm for the cross-section enumeration problem that is linear in n+t$n+t$, where t$t$ is the output size. We provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. We discuss some shortcomings of the enumeration algorithm found in the Grail computation package. In the practical domain, we modify Mäkinen’s enumeration algorithm to get an algorithm that is usually the most efficient in practice. We performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable.