Relations of contextual grammars with strictly locally testable selection languages

DOI10.1051/ITA/2023012arXiv2208.14725OpenAlexW4388641234MaRDI QIDQ6186541FDOQ6186541

Authors: Jürgen Dassow, Bianca Truthe 

Publication date: 2 February 2024

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiple-entry finite automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On external contextual grammars with subregular selection languages
• Power-separating regular languages
• The Theory of Definite Automata
• From regular to strictly locally testable languages
• Aspects of Molecular Computing
• Title not available (Why is that?)
• On subregular selection languages in internal contextual grammars
• Remarks on external contextual grammars with selection
• Grammars with control by ideals and codes

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)