Cover Image

A short survey around the pumping lemma for context-free languages

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Gullà, Gabriele
Format:	Preprint
Published:	2024
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A pumping-like lemma for languages over infinite alphabets
by: Danieli, Yoav
Published: (2025)

Quantum finite automata and linear context-free languages: a decidable problem
by: Bertoni, A., et al.
Published: (2013)

A substitution lemma for multiple context-free languages
by: Duncan, Andrew, et al.
Published: (2025)

Bounded treewidth, multiple context-free grammars, and downward closures
by: Aiswarya, C., et al.
Published: (2025)

Navigational hierarchies of regular languages
by: Place, Thomas, et al.
Published: (2024)

Geodesic languages for rational subsets and conjugates in virtually free groups
by: Carvalho, André, et al.
Published: (2024)

On state complexity for subword-closed languages
by: Guyot, Jérôme
Published: (2024)

Note on dissecting power of regular languages
by: Rukavicka, Josef
Published: (2023)

Two-way affine automata can verify every language
by: Chen, Zeyu, et al.
Published: (2025)

Passive Model Learning of Visibly Deterministic Context-free Grammars
by: Muškardin, Edi, et al.
Published: (2025)

Characterization of deterministically recognizable weighted tree languages over commutative semifields by finitely generated and cancellative scalar algebras
by: Fülöp, Zoltán, et al.
Published: (2025)

Congruence based proofs of the recognizability theorems for free many-sorted algebras
by: Vidal, Juan Climent, et al.
Published: (2018)

A language-theoretic approach to study the density of subsets in free groups
by: Carvalho, André
Published: (2026)

Dissecting power of intersection of two context-free languages
by: Rukavicka, Josef
Published: (2020)

Finite-valued Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2024)

Watson-Crick conjugates of words and languages
by: Mahalingam, Kalpana, et al.
Published: (2022)

Automata-based constraints for language model decoding
by: Koo, Terry, et al.
Published: (2024)

Regular language quantum states
by: Florido-Llinàs, Marta, et al.
Published: (2024)

Sequential densities of rational languages
by: Gorman, Alexi Block, et al.
Published: (2026)

A Close Analysis of the Subset Construction
by: Baburin, Ivan, et al.
Published: (2024)

Permutation closure for multiple context-free languages
by: Duncan, Andrew, et al.
Published: (2025)

Corrections to A Menagerie of Timed Automata
by: Keiren, Jeroen J. A., et al.
Published: (2016)

A Unifying Approach to Picture Automata
by: Meeres, Yvo Ad, et al.
Published: (2025)

A Variety of Request-Response Specifications
by: Aiba, Daichi, et al.
Published: (2025)

A Factorization Theorem for Forest Algebras
by: Almagor, Shaull, et al.
Published: (2026)

A model of actors and grey failures
by: Bocchi, Laura, et al.
Published: (2022)

A Formal Approach for Tuning Stochastic Oscillators
by: Ballarini, Paolo, et al.
Published: (2024)

A Tree Sampler for Bounded Context-Free Languages
by: Considine, Breandan
Published: (2024)

FocusE: A semantic extension of FocusST
by: Spichkova, Maria
Published: (2025)

A General Information Extraction Framework Based on Formal Languages
by: Schmid, Markus L.
Published: (2025)

A Linear-time Simulation of Deterministic $d$-Limited Automata
by: Rubtsov, Alexander
Published: (2023)

A Probabilistic Model-Checking Framework for Cognitive Assessment and Training
by: De Maria, Elisabetta, et al.
Published: (2026)

A Characterization of Turing Machines that Compute Primitive Recursive Functions
by: Schwartz, Daniel G.
Published: (2025)

A Usage-Aware Sequent Calculus for Differential Dynamic Logic
by: Dotzel, Myra, et al.
Published: (2023)

A Regular and Complete Notion of Delay for Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2022)

A Complexity Bound for Determinisation of Min-Plus Weighted Automata
by: Almagor, Shaull, et al.
Published: (2026)

A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation
by: Akshay, S, et al.
Published: (2023)

A quadratic lower bound for 2DFAs against one-way liveness
by: Adeogun, Kehinde, et al.
Published: (2026)

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
by: Bergsträßer, Pascal, et al.
Published: (2024)

Frequency Automata: A novel formal model of hybrid systems in combined time and frequency domains
by: Kim, Moon, et al.
Published: (2025)