Parallel Accepting Colonies: Computational Power and Deterministic Parsing
摘要
In the framework of formal languages, colonies are understood as teams of simple rewriting agents acting on strings of symbols. They were introduced as formal devices generating sets of strings (i.e., formal languages) from a given axiom. We study variants of colonies acting as parallel language acceptors, i.e., characterizing formal languages by their reduction to the axiom. We first show that the class of languages these colonies accept in the weakly competitive mode strictly contains the class of context-free languages. Then we focus on their possible applications in parallel parsing of formal languages. We construct a class of restricted parallel accepting colonies for which there exists a deterministic parsing algorithm working in polynomial time.