On the decidability of infix inclusion problem

DOI10.1007/S00224-023-10160-WMaRDI QIDQ6580072zbMATH OpenFDO

Authors Hyunjoon Cheon, Joonghyuk Hahn, Yo-Sub Han

Publication date 29 July 2024

Published in Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

decidabilityformal languagesinfix inclusion

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

• 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?)
• A survey on operational state complexity
• Alternation
• Analyzing catastrophic backtracking behavior in practical regular expression matching
• Computational Complexity
• Distinguishability operations and closures
• Efficient inclusion checking for deterministic tree automata and XML schemas
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Equivalence and inclusion problem for strongly unambiguous Büchi automata
• Input-driven pushdown automata for edit distance neighborhood
• On the decidability of infix inclusion problem
• 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

(1)

• On the decidability of infix inclusion problem

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 Q6580072)