Cover Image

A pumping-like lemma for languages over infinite alphabets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Danieli, Yoav
Format:	Preprint
Published:	2025
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

Star Complexity of Parikh Images of Languages over Infinite Alphabets
by: Danieli, Yoav
Published: (2026)

A short survey around the pumping lemma for context-free languages
by: Gullà, Gabriele
Published: (2024)

The single-use restriction for register automata and transducers over infinite alphabets
by: Stefański, Rafał
Published: (2024)

The complexity of finite smooth words over binary alphabets
by: Cassaigne, Julien, et al.
Published: (2026)

Deterministic Parikh automata on infinite words
by: Grobler, Mario, et al.
Published: (2024)

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)

Reduced complexities for sequences over finite alphabets
by: Campbell, John M., et al.
Published: (2025)

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

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

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

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

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

Distribution of Reconfiguration Languages maintaining Tree-like Communication Topology
by: Hausmann, Daniel, et al.
Published: (2024)

Reversible Transducers over Infinite Words
by: Dartois, Luc, et al.
Published: (2024)

Minimizing Cost Register Automata over a Field
by: Benalioua, Yahia Idriss, et al.
Published: (2023)

Verification under TSO with an infinite Data Domain
by: Abdulla, Parosh Aziz, et al.
Published: (2024)

Soft state reduction of fuzzy automata over residuated lattices
by: Nguyen, Linh Anh, et al.
Published: (2025)

Learning Weighted Automata over Number Rings, Concretely and Categorically
by: Aristote, Quentin, et al.
Published: (2025)

Reversible Weighted Automata over Finite Rings and Monoids with Commuting Idempotents
by: Kostolányi, Peter, et al.
Published: (2026)

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)

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

The Complexity of Aggregates over Extractions by Regular Expressions
by: Doleschal, Johannes, et al.
Published: (2020)

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

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

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

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 Close Analysis of the Subset Construction
by: Baburin, Ivan, et al.
Published: (2024)

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

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)

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

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

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

A Characterization of Turing Machines that Compute Primitive Recursive Functions
by: Schwartz, Daniel G.
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 Usage-Aware Sequent Calculus for Differential Dynamic Logic
by: Dotzel, Myra, et al.
Published: (2023)