Cover Image

The Equivalence Problem of E-Pattern Languages with Regular Constraints is Undecidable

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nowotka, Dirk, Wiedenhöft, Max
Format:	Preprint
Published:	2024
Subjects:	Formal Languages and Automata Theory Computational Complexity Combinatorics 68R15 F.4.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Equivalence Problem of E-Pattern Languages with Length Constraints is Undecidable
by: Nowotka, Dirk, et al.
Published: (2024)

An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints
by: Jansen, Klaus, et al.
Published: (2025)

Tight Bounds for the Number of Absent Subsequences
by: Adamson, Duncan, et al.
Published: (2024)

The decidability of the genus of regular languages and directed emulators
by: Bonfante, Guillaume, et al.
Published: (2021)

Some Remarks on Marginal Code Languages
by: Konstantinidis, Stavros
Published: (2026)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
by: Cho, Da-Jung, et al.
Published: (2025)

Decision Problems on Copying and Shuffling
by: Halava, Vesa, et al.
Published: (2023)

Deciding Sparseness of Regular Languages of Finite Trees and Infinite Words
by: Eickmeyer, Kord, et al.
Published: (2025)

On the Equivalence Checking Problem for Deterministic Top-Down Tree Automata
by: Deng, Zhibo, et al.
Published: (2025)

Programmable Co-Transcriptional Splicing: Realizing Regular Languages via Hairpin Deletion
by: Cho, Da-Jung, et al.
Published: (2025)

Omega-Regular Robustness
by: Fisman, Dana, et al.
Published: (2025)

Geometric Characterization of Context-Free Intersections via the Inner Segment Dichotomy
by: Silva, Jorge Miguel
Published: (2026)

How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars
by: Havel, Martin, et al.
Published: (2024)

Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
by: Rote, Günter
Published: (2024)

Algebraic Language Theory with Effects
by: Lenke, Fabian, et al.
Published: (2024)

Eve-positional languages: putting order into Büchi automata
by: Idir, Olivier
Published: (2026)

Decomposition of Automata recognizing Ideals
by: Berry, Mathias, et al.
Published: (2026)

On universality of regular realizability problems
by: Rubtsov, Alexander, et al.
Published: (2023)

Learning Automata with Name Allocation
by: Frank, Florian, et al.
Published: (2025)

Alternating Nominal Automata with Name Allocation
by: Frank, Florian, et al.
Published: (2024)

Using games and universal trees to characterise the nondeterministic index of tree languages
by: Idir, Olivier, et al.
Published: (2025)

Nominal Tree Automata With Name Allocation
by: Prucker, Simon, et al.
Published: (2024)

An algebraic characterisation of Eve-positional languages
by: Colcombet, Thomas, et al.
Published: (2026)

Generalized Parikh Matrices For Tracking Subsequence Occurrences
by: Fazekas, Szilárd Zsolt, et al.
Published: (2024)

Store Languages of Turing Machines and Counter Machines
by: Friesen, Noah, et al.
Published: (2025)

Normal Forms for Elements of ${}^*$-Continuous Kleene Algebras Representing the Context-Free Languages
by: Hopkins, Mark, et al.
Published: (2023)

On the probability of being synchronizable
by: Berlinkov, Mikhail V.
Published: (2013)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
by: Esparza, Javier, et al.
Published: (2025)

Subword enumeration up to stack-sorting equivalence
by: Campbell, John M., et al.
Published: (2026)

Low complexity binary words avoiding $(5/2)^+$-powers
by: Currie, James, et al.
Published: (2025)

Computing the k-binomial complexity of generalized Thue--Morse words
by: Golafshan, M., et al.
Published: (2024)

Mapping words to powers by morphisms
by: Saarela, Aleksi
Published: (2025)

A Connection Between Unbordered Partial Words and Sparse Rulers
by: Saarela, Aleksi, et al.
Published: (2024)

Mapped Exponent and Asymptotic Critical Exponent of Words
by: Foster, Eva, et al.
Published: (2025)

Group Actions and Some Combinatorics on Words with $\mathbf{vtm}$
by: Machacek, John
Published: (2025)

The Shortest Interesting Binary Words
by: Fici, Gabriele
Published: (2024)

Well-Quasi-Orderings on Word Languages
by: Lhote, Nathan, et al.
Published: (2025)

Anti-Context-Free languages
by: Cardó, Carles
Published: (2024)

Commuting upper triangular binary morphisms
by: Honkala, Juha
Published: (2023)

Active Learning Techniques for Pomset Recognizers
by: Pommellet, Adrien, et al.
Published: (2025)