2025
Parallel Accepting Colonies: Computational Power and Deterministic Parsing
SOSÍK, Petr and Lucie CIENCIALOVÁBasic information
Original name
Parallel Accepting Colonies: Computational Power and Deterministic Parsing
Authors
Edition
15840. vyd. Cham, Languages of Cooperation and Communication, p. 103-116, 14 pp. Lecture Notes in Computer Science, 2025
Publisher
Springer
Other information
Language
English
Type of outcome
Chapter(s) of a specialized book
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Germany
Confidentiality degree
is not subject to a state or trade secret
Publication form
electronic version available online
References:
Organization unit
Faculty of Philosophy and Science in Opava
ISBN
978-3-031-97273-7
EID Scopus
2-s2.0-105010611208
Keywords in English
Deterministic parsing; Grammar system; Parallel colony
Tags
International impact, Reviewed
Changed: 18/12/2025 09:12, Mgr. Kamil Matula, Ph.D.
Abstract
In the original language
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.