Complexity of bifix-free regular languages

DOI10.1007/978-3-319-60134-2_7MaRDI QIDQ5920053zbMATH OpenOpenAlexFDO

Authors Robert Ferens, Marek Szykuła

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

bifix-freemost complexprefix-freestate complexitysuffix-freetransition semigroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Complexity of bifix-free regular languages
• Syntactic complexity of bifix-free regular languages
• Quotient complexity of bifix-, factor-, and subword-free regular languages
• Syntactic complexity of bifix-free languages
• Quotient complexity of bifix-, factor-, and subword-free regular languages

Cites work

• Codes and automata.
• Complexity of atoms, combinatorially
• Complexity of bifix-free regular languages
• Complexity of proper prefix-convex regular languages
• Complexity of suffix-free regular languages
• Decision problems for convex languages
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• In search of most complex 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 languages
• Quotient complexity of regular languages
• Reversal on regular languages and descriptional complexity
• State complexity of basic operations on non-returning regular languages
• Syntactic complexity of bifix-free languages
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Theory of átomata

Cited in

(11)

• Syntactic complexity of bifix-free regular languages
• Syntactic complexity of bifix-free languages
• Complexity in union-free regular languages
• Complexity of suffix-free regular languages
• Complexity in Union-Free Regular Languages
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• scientific article; zbMATH DE number 7315105 (Why is no real title available?)
• Quotient complexity of bifix-, factor-, and subword-free regular languages
• Quotient complexity of bifix-, factor-, and subword-free regular languages
• Complexity of bifix-free regular languages
• Complexity of bifix-free regular languages

Describes a project that uses

Uses Software

• GAP

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5920053)