Complexity of bifix-free regular languages

DOI10.1016/j.tcs.2018.09.016zbMath1429.68110arXiv1701.03768OpenAlexW3023815151MaRDI QIDQ5919577

Marek Szykuła, Robert Ferens

Publication date: 20 August 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

productregular languageBoolean operationstransition semigroupstate complexityreversalbifix-freeprefix-freesuffix-freesyntactic complexitymagic numbermost complexquotient complexityatom complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

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
• Complexity of proper suffix-convex regular languages
• Syntactic complexity of bifix-free languages
• Most complex non-returning regular 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 atoms, combinatorially

This page was built for publication: Complexity of bifix-free regular languages