Parallel Accepting Colonies: Computational Power and
Deterministic Parsing

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

Autoři

SOSÍK, Petr a Lucie CIENCIALOVÁ

Vydání

15840. vyd. Cham, Languages of Cooperation and Communication, od s. 103-116, 14 s. Lecture Notes in Computer Science, 2025

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Kapitola resp. kapitoly v odborné knize

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

Spinger Nature Link - domovská stránka výsledku

Organizační jednotka

Filozoficko-přírodovědecká fakulta v Opavě

ISBN

978-3-031-97273-7

DOI

https://doi.org/10.1007/978-3-031-97274-4_7

EID Scopus

2-s2.0-105010611208

Klíčová slova anglicky

Deterministic parsing; Grammar system; Parallel colony

Štítky

2025, RIV26, SGS92024, ÚI

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 18. 12. 2025 09:12, Mgr. Kamil Matula, Ph.D.

Anotace

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.

Citovat

SOSÍK, Petr a Lucie CIENCIALOVÁ. Parallel Accepting Colonies: Computational Power and Deterministic Parsing. Online. In Jiménez López, M. D.; Vaszil, G. Languages of Cooperation and Communication. 15840. vyd. Cham: Springer, 2025, s. 103-116. Lecture Notes in Computer Science. ISBN 978-3-031-97273-7. Dostupné z: https://doi.org/10.1007/978-3-031-97274-4_7.

@inbook{89302,
   author = {Sosík, Petr and Ciencialová, Lucie},
   address = {Cham},
   booktitle = {Languages of Cooperation and Communication},
   doi = {https://doi.org/10.1007/978-3-031-97274-4_7},
   edition = {15840},
   editor = {Jiménez López, M. D.; Vaszil, G.},
   keywords = {Deterministic parsing; Grammar system; Parallel colony},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-031-97273-7},
   pages = {103-116},
   publisher = {Springer},
   title = {Parallel Accepting Colonies: Computational Power and Deterministic Parsing},
   url = {https://link.springer.com/chapter/10.1007/978-3-031-97274-4_7},
   year = {2025}
}

TY  - CHAP
ID  - 89302
AU  - Sosík, Petr - Ciencialová, Lucie
PY  - 2025
TI  - Parallel Accepting Colonies: Computational Power and Deterministic Parsing
VL  - Lecture Notes in Computer Science
PB  - Springer
CY  - Cham
SN  - 9783031972737
KW  - Deterministic parsing
KW  - Grammar system
KW  - Parallel colony
UR  - https://link.springer.com/chapter/10.1007/978-3-031-97274-4_7
N2  - 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.
ER  -

SOSÍK, Petr a Lucie CIENCIALOVÁ. Parallel Accepting Colonies: Computational Power and Deterministic Parsing. Online. In Jiménez López, M. D.; Vaszil, G. \textit{Languages of Cooperation and Communication}. 15840. vyd. Cham: Springer, 2025, s.~103-116. Lecture Notes in Computer Science. ISBN~978-3-031-97273-7. Dostupné z: https://doi.org/10.1007/978-3-031-97274-4\_{}7.

Přehled o publikaci