2017/08/21 by Alexander Meduna, Jakub Martiško
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Affix grammar #Algorithms and Data Compression #Component (thermodynamics) #Computer science #Context (archaeology) #Context-free grammar #Context-sensitive grammar #DNA and Biological Computing #Extended Affix Grammar #Geography #Grammar #Linguistics #Natural language processing #Operator-precedence grammar #Philosophy #Physics #Rule-based machine translation #cs.FL
paper · pdf · doi:10.4204/eptcs.252.17
published as EPTCS 252, 2017, pp. 170-179 · In Proceedings AFL 2017, arXiv:1708.06226
openalex publication_date 2017/08/21 · arxiv created 2017/08/22 · arxiv updated 2017/08/23 · openalex created_date 2017/08/31 · openalex updated_date 2026/08/05
The L(PSCG)=L(CS) problem asks whether propagating scattered context grammars and context sensitive grammars are equivalent. The presented paper reformulates and answers this problem in terms of CD grammar systems. More specifically, it characterizes the family of context sensitive languages by two-component CD grammar systems with propagating scattered context rules.