C
2025
Parallel Accepting Colonies: Computational Power and Deterministic Parsing
SOSÍK, Petr a Lucie CIENCIALOVÁ
Základní údaje
Originální název
Parallel Accepting Colonies: Computational Power and Deterministic Parsing
Vydání
15840. vyd. Cham, Languages of Cooperation and Communication, od s. 103-116, 14 s. Lecture Notes in Computer Science, 2025
Další údaje
Typ výsledku
Kapitola resp. kapitoly v odborné knize
Obor
10201 Computer sciences, information science, bioinformatics
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
elektronická verze "online"
Organizační jednotka
Filozoficko-přírodovědecká fakulta v Opavě
EID Scopus
2-s2.0-105010611208
Klíčová slova anglicky
Deterministic parsing; Grammar system; Parallel colony
Příznaky
Mezinárodní význam, Recenzováno
V originále
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.
Zobrazeno: 30. 1. 2026 06:55