Nondeterministic State Complexity of Positional Addition

Details Nondeterministic State Complexity of Positional Addition Nondeterministic State Complexity of Positional Addition

2009-07-29

arxiv.org/abs/0907.5072v1

EPTCS 3, 2009, pp. 151-161

Computer Science

Formal Languages and Automata Theory

Scientific paper

10.4204/EPTCS.3.14

Consider nondeterministic finite automata recognizing base-k positional notation of numbers. Assume that numbers are read starting from their least significant digits. It is proved that if two sets of numbers S and T are represented by nondeterministic automata of m and n states, respectively, then their sum {s+t | s in S, t in T} is represented by a nondeterministic automaton with 2mn+2m+2n+1 states. Moreover, this number of states is necessary in the worst case for all k>=9.

Affiliated with

Also associated with

No associations

Rating

Nondeterministic State Complexity of Positional Addition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nondeterministic State Complexity of Positional Addition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nondeterministic State Complexity of Positional Addition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521416