On the decidability of infix inclusion problem

DOI10.1007/978-3-031-05578-2_9MaRDI QIDQ2163987zbMATH OpenOpenAlexFDO

Authors Hyunjoon Cheon, Joonghyuk Hahn, Yo-Sub Han

Publication date 11 August 2022

Full work available at URL https://doi.org/10.1007/978-3-031-05578-2_9

zbMATH Keywords

context-free languagesdecidabilityinfix inclusionregular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the decidability of infix inclusion problem
• Inclusion is undecidable for pattern languages
• Decision problems for patterns
• Bad News on Decision Problems for Patterns
• Bad news on decision problems for patterns

Cites work

• A survey on operational state complexity
• Alternation
• Analyzing catastrophic backtracking behavior in practical regular expression matching
• Computational Complexity
• Distinguishability operations and closures
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Equivalence and inclusion problem for strongly unambiguous Büchi automata
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 7453188 (Why is no real title available?)
• scientific article; zbMATH DE number 3251424 (Why is no real title available?)
• On the density of context-free and counter languages
• Programming Techniques: Regular expression search algorithm
• State complexity of code operators
• State complexity of prefix, suffix, bifix and infix operators on regular languages
• Static detection of DoS vulnerabilities in programs that use regular expressions
• Visibly pushdown automata: universality and inclusion via antichains
• Visibly pushdown languages

Cited in

(3)

• A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
• How to settle the ReDoS problem: back to the classical automata theory
• On the decidability of infix inclusion problem

Describes a project that uses

Uses Software

• Python

This page was built for publication: On the decidability of infix inclusion problem

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