Detecting palindromes, patterns and borders in regular languages

DOI10.1016/j.ic.2008.06.007zbMath1192.68403OpenAlexW1982678879MaRDI QIDQ1041028

J. Blot

Publication date: 27 November 2009

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.06.007

zbMATH Keywords

palindromepatternprimitive wordbordered word\(k\)-power

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On regular realizability problems for context-free languages ⋮ Properties of graphs specified by a regular language ⋮ Properties of graphs specified by a regular language ⋮ On expressive power of regular realizability problems ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Detecting patterns in finite regular and context-free languages ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ On the decidability of finding a positive ILP-instance in a regular set of ILP-instances ⋮ From decidability to undecidability by considering regular sets of instances ⋮ Regular Realizability Problems and Context-Free Languages ⋮ Automata equipped with auxiliary data structures and regular realizability problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Linear prime-number sieves: A family tree
• Finite automata and unary languages
• Automata accepting primitive words
• Intersection and union of regular languages and state complexity
• Numeration systems, linear recurrences, and regular sets
• Patterns in words and languages
• Automaticity. I: Properties of a measure of descriptional complexity
• Automata, Boolean matrices, and ultimate periodicity.
• Thin and slender languages
• Relationships between nondeterministic and deterministic tape complexities
• Efficient Enumeration of Regular Languages
• The Maximum Order of an Element of a Finite Symmetric Group
• Fast Pattern Matching in Strings
• Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
• H-bounded and semi-discrete languages
• Theory Is Forever