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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Parallel Accepting Colonies: Computational Power and Deterministic Parsing

  • Petr Sosík,
  • Lucie Ciencialová

摘要

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.