Relations of contextual grammars with strictly locally testable selection languages

DOI10.1051/ITA/2023012MaRDI QIDQ6186541zbMATH OpenOpenAlexFDO

Authors Jürgen Dassow, Bianca Truthe

Publication date 2 February 2024

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2208.14725

zbMATH Keywords

contextual grammarsexternal and internal derivation modesselection languagessubregular families of languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Abstract: We continue the research on the generative capacity of contextual grammars where contexts are adjoined around whole words (externally) or around subwords (internally) which belong to special regular selection languages. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We investigate contextual grammars with strictly locally testable selection languages and compare those families to families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages.

Cites work

• scientific article; zbMATH DE number 2182422 (Why is no real title available?)
• scientific article; zbMATH DE number 50943 (Why is no real title available?)
• scientific article; zbMATH DE number 3473324 (Why is no real title available?)
• scientific article; zbMATH DE number 3596263 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3293675 (Why is no real title available?)
• scientific article; zbMATH DE number 3307580 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Aspects of Molecular Computing
• From regular to strictly locally testable languages
• Grammars with control by ideals and codes
• Multiple-entry finite automata
• On external contextual grammars with subregular selection languages
• On subregular selection languages in internal contextual grammars
• Power-separating regular languages
• Remarks on external contextual grammars with selection
• The Theory of Definite Automata

This page was built for publication: Relations of contextual grammars with strictly locally testable selection languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6186541)