Detecting patterns in finite regular and context-free languages

DOI10.1016/J.IPL.2009.11.002MaRDI QIDQ990125zbMATH OpenOpenAlexFDO

Authors Narad Rampersad, Jeffrey Shallit

Publication date 2 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.3220

zbMATH Keywords

regular languageformal languagespattern matchingcontext-free languagefinite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Pattern recognition, speech recognition (68T10) Searching and sorting (68P10)

Abstract: We consider variations on the following problem: given an NFA M and a pattern p, does there exist an x in L(M) such that p matches x? We consider the restricted problem where M only accepts a finite language. We also consider the variation where the pattern p is required only to match a factor of x. We show that both of these problems are NP-complete. We also consider the same problems for context-free grammars; in this case the problems become PSPACE-complete.

Recommendations

• Pattern matching with variables: fast algorithms and new hardness results
• State complexity of pattern matching in regular languages
• scientific article; zbMATH DE number 7278096
• Pattern matching with variables: efficient algorithms and complexity results
• scientific article; zbMATH DE number 1836426

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• 2726. A problem on strings of beads
• Detecting palindromes, patterns and borders in regular languages
• Finding a homomorphism between two words is NP-complete
• Finding patterns common to a set of strings

Cited in

(9)

• Prefix-free regular languages and pattern matching
• Regular and Context-Free Pattern Languages over Small Alphabets
• Regular and context-free pattern languages over small alphabets
• Factors of generalised polynomials and automatic sequences
• Decision problems on copying and shuffling
• A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems
• Regular patterns, regular languages and context-free languages
• Finite Automata, Palindromes, Powers, and Patterns
• scientific article; zbMATH DE number 1836426 (Why is no real title available?)

This page was built for publication: Detecting patterns in finite regular and context-free languages

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