Detecting patterns in finite regular and context-free languages

DOI10.1016/J.IPL.2009.11.002zbMATH Open1206.68181arXiv0906.3220OpenAlexW2056080555MaRDI QIDQ990125FDOQ990125

Authors: Narad Rampersad, Jeffrey Shallit 

Publication date: 2 September 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Finding patterns common to a set of strings
• Title not available (Why is that?)
• Finding a homomorphism between two words is NP-complete
• Detecting palindromes, patterns and borders in regular languages
• 2726. A problem on strings of beads

Cited In (9)

• Factors of generalised polynomials and automatic sequences
• A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems
• Decision problems on copying and shuffling
• 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
• Finite Automata, Palindromes, Powers, and Patterns
• Title not available (Why is that?)
• Regular patterns, regular languages and context-free languages

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)