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

DOI10.14232/ACTACYB.21.4.2014.1zbMATH Open1324.68055OpenAlexW136331652MaRDI QIDQ5250874FDOQ5250874

Authors:

Publication date: 22 May 2015

Published in: Acta Cybernetica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.14232/actacyb.21.4.2014.1

Recommendations

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

zbMATH Keywords

regular languagefinite automatonstate complexitybifix-freefactor-freetight upper boundquotient complexitysubword-free

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (23)

• Quotient complexity of bifix-, factor-, and subword-free regular languages
• The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
• Prefix-free subsets of regular languages and descriptional complexity
• Quotient complexity of regular languages
• Factorial languages with quadratically upper bounded growth functions and nonlinearly upper bounded subword complexities
• The cut operation in subclasses of convex languages
• Nondeterministic state complexity of star-free languages
• Power, positive closure, and quotients on convex languages
• Closure properties of subregular languages under operations
• Complexity of bifix-free regular languages
• Complexity of bifix-free regular languages
• Prefix-free languages: right quotient and reversal
• Nondeterministic complexity of operations on free and convex languages
• Nondeterministic complexity in subclasses of convex languages
• Prefix-free languages: left and right quotient and reversal
• Operational complexity in subregular classes
• The cut operation in subclasses of convex languages (extended abstract)
• Quotient complexity of star-free languages
• On the computation of quotients and factors of regular languages
• Syntactic complexity of bifix-free regular languages
• Complexity of suffix-free regular languages
• Complexity of suffix-free regular languages
• Generalizations of Code Languages with Marginal Errors

This page was built for publication: Quotient complexity of bifix-, factor-, and subword-free regular languages

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