On the computational and descriptional complexity of multi-pattern languages

DOI10.1016/J.TCS.2025.115063MaRDI QIDQ7028336zbMATH OpenFDO

Authors Jingnan Xie, H. B. III Hunt, R. E. Stearns

Publication date 12 February 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115063

zbMATH Keywords

computational complexitydescriptional complexityextended regular expressionsmulti-pattern languagesundecidabilityuniversality problem

Mathematics Subject Classification ID

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

Cites work

• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Bounded languages described by GF(2)-grammars
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity of formal systems
• Descriptional complexity of machines with limited resources
• Extended regular expressions: succinctness and decidability
• Extending regular expressions with homomorphic replacement
• Finding patterns common to a set of strings
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 4124977 (Why is no real title available?)
• Learning in the limit with lattice-structured hypothesis spaces
• Multi-pattern languages
• On bounded languages and reversal-bounded automata
• On the equivalence, containment, and covering problems for the regular and context-free languages
• On the undecidability and descriptional complexity of synchronized regular expressions
• Parameterized regular expressions and their languages
• Pattern languages with and without erasing
• Pattern-based rewriting through abstraction
• Pumping lemmas can be ``harmful
• Special section on descriptional complexity of formal systems
• The complexity of theorem-proving procedures
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS

Cited in

(2)

• Decision problems concerning L systems
• A practical extension of computational complexity theory for applications in mathematics and sciences

This page was built for publication: On the computational and descriptional complexity of multi-pattern languages

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