Representing and computing regular languages on massively parallel networks.

Area of Science:

• Computational linguistics
• Statistical inference
• Computer vision

Background:

• Stochastic inference and rule-based constraints are often treated separately.
• Existing methods lack a unified framework for integrating syntactic and stochastic pattern recognition.
• Generalizing Shannon's work on channel encoding to maximum entropy Markov chains is a key theoretical development.

Purpose of the Study:

• To propose a general method for incorporating rule-based constraints from regular languages into stochastic inference problems.
• To establish a formal connection between rules and Chomsky grammars.
• To enable a unified representation of stochastic and syntactic pattern constraints.

Main Methods:

• Generalizing Shannon's encoding of rule-based sequences to maximum entropy Markov chains.
• Developing a maximum entropy probabilistic view leading to Gibbs representations.
• Coupling Gibbs representations to stochastic diffusion algorithms for sampling language-constrained sequences.
• Deriving parallel stochastic cellular automata for generating samples from rule-based constraint sets.

Main Results:

• A unified representation for stochastic and syntactic pattern constraints is achieved.
• The number of minima in Gibbs representations grows exponentially with the language complexity.
• Fully parallel stochastic cellular automata are derived for generating rule-constrained sequences.
• The method was successfully mapped to the DAP-510 massively parallel processor for image segmentation.

Conclusions:

• The proposed method offers a unified framework for integrating rule-based and stochastic constraints in pattern recognition.
• The derived stochastic cellular automata are efficient for generating complex, rule-governed data.
• This approach has practical applications in areas like automated image segmentation using massively parallel processing.