Regular patterns, regular languages and context-free languages

DOI10.1016/J.IPL.2010.09.010zbMath1379.68224OpenAlexW2090869915MaRDI QIDQ1675877

Sanjay Jain, Yuh Shin Ong, Frank Stephan

Publication date: 3 November 2017

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.09.010

zbMATH Keywords

regular languagescontext free languagespattern languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Closure properties of pattern languages ⋮ Word equations in the context of string solving ⋮ Distinguishing pattern languages with membership examples ⋮ Regular and context-free pattern languages over small alphabets ⋮ The complexity of verbal languages over groups ⋮ Finitely distinguishable erasing pattern languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time inference of arbitrary pattern languages
• A non-learnable class of E-pattern languages
• Bad news on decision problems for patterns
• Finding patterns common to a set of strings
• Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time
• An introduction to Kolmogorov complexity and its applications
• Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries

This page was built for publication: Regular patterns, regular languages and context-free languages