Complexity of bifix-free regular languages

DOI10.1007/978-3-319-60134-2_7zbMath1429.68109OpenAlexW2732271419MaRDI QIDQ5920053

Marek Szykuła, Robert Ferens

Publication date: 22 August 2017

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-60134-2_7

zbMATH Keywords

transition semigroupstate complexitybifix-freeprefix-freesuffix-freemost complex

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Syntactic complexity of bifix-free languages, Complexity of bifix-free regular languages, Syntactic complexity of bifix-free regular languages

Uses Software

• GAP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Decision problems for convex languages
• Syntactic complexity of bifix-free languages
• Theory of átomata
• Reversal on Regular Languages and Descriptional Complexity
• Complexity of Suffix-Free Regular Languages
• State Complexity of Basic Operations on Non-Returning Regular Languages
• Kleene Closure on Regular and Prefix-Free Languages
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages
• Quotient Complexity of Bifix-, Factor-, and Subword-free Regular Language
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• Complexity of proper prefix-convex regular languages
• Complexity of bifix-free regular languages
• Complexity of atoms, combinatorially