Efficient Divide-and-Conquer Implementations Of Symmetric FSAs

Details Efficient Divide-and-Conquer Implementations Of Symmetric FSAs Efficient Divide-and-Conquer Implementations Of Symmetric FSAs

2007-08-03

arxiv.org/abs/0708.0580v3

Journal of Cellular Automata 5(6) (special issue for Automata 2007, H. Fuks & A. T. Lawniczak, eds), pages 481-490, 2010

Computer Science

Formal Languages and Automata Theory

Scientific paper

A deterministic finite-state automaton (FSA) is an abstract sequential machine that reads the symbols comprising an input word one at a time. An FSA is symmetric if its output is independent of the order in which the input symbols are read, i.e., if the output is invariant under permutations of the input. We show how to convert a symmetric FSA A into an automaton-like divide-and-conquer process whose intermediate results are no larger than the size of A's memory. In comparison, a similar result for general FSA's has been long known via functional composition, but entails an exponential increase in memory size. The new result has applications to parallel processing and symmetric FSA networks.

Affiliated with

Also associated with

No associations

Rating

Efficient Divide-and-Conquer Implementations Of Symmetric FSAs 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 Efficient Divide-and-Conquer Implementations Of Symmetric FSAs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Divide-and-Conquer Implementations Of Symmetric FSAs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-499820