Pumping lemmas for classes of languages generated by folding systems

DOI10.1007/S11047-019-09771-5MaRDI QIDQ6095498zbMATH OpenWikidataFDO

Authors Jorge C. Lucero

Publication date 8 September 2023

Published in Natural Computing (Search for Journal in Brave)

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

zbMATH Keywords

F-systemfoldingformal languagepumping lemma

Mathematics Subject Classification ID

Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07) Formal languages and automata (68Q45)

Abstract: Geometric folding processes are ubiquitous in natural systems ranging from protein biochemistry to patterns of insect wings and leaves. In a previous study, a folding operation between strings of formal languages was introduced as a model of such processes. The operation was then used to define a folding system (F-system) as a construct consisting of a core language, containing the strings to be folded, and a folding procedure language, which defines how the folding is done. This paper reviews main definitions associated with F-systems and next it determines necessary conditions for a language to belong to classes generated by such systems. The conditions are stated in the form of pumping lemmas and four classes are considered, in which the core and folding procedure languages are both regular, one of them is regular and the other context-free, or both are context-free. Full demonstrations of the lemmas are provided, and the analysis is illustrated with examples.

Recommendations

• A pumping lemma for flip-pushdown languages
• scientific article; zbMATH DE number 18637
• Pumping Lemma for Higher-order Languages
• Pumping lemmas for linear and nonlinear context-free languages
• Pumping lemmas for special linear languages
• Formalization of the pumping lemma for context-free languages
• A pumping lemma for \textbf{DLI}-languages
• A pumping lemma for deterministic context-free languages
• Some applications of the formalization of the pumping lemma for context-free languages
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages

Cites work

• A mathematical theory of origami constructions and numbers
• Computing transparently: The independent sets in a graph
• Geometric folding algorithms. Linkages, origami, polyhedra
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• On multiple context-free grammars
• Shuffle on trajectories: Syntactic constraints
• The failure of the strong pumping lemma for multiple context-free languages

Cited in

(5)

• A note on the class of languages generated by F-systems over regular languages
• Pumping lemmas for special linear languages
• scientific article; zbMATH DE number 18637 (Why is no real title available?)
• Pumping Lemma for Higher-order Languages
• Pumping lemmas can be ``harmful

This page was built for publication: Pumping lemmas for classes of languages generated by folding systems

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