Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages

DOI10.1016/J.TCS.2012.04.011MaRDI QIDQ443735zbMATH OpenOpenAlexFDO

Authors Baiyu Li, Yuli Ye, Janusz Brzozowski

Publication date 13 August 2012

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

Full work available at URL https://doi.org/10.1016/j.tcs.2012.04.011

zbMATH Keywords

regular languagesemigroupmonoidfinite automatonreversalbifix-freefactor-freeprefix-freesuffix-freesyntactic complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Recommendations

• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• Syntactic complexity of bifix-free regular languages
• scientific article; zbMATH DE number 7315105
• Complexity of bifix-free regular languages
• Complexity of bifix-free regular languages
• Syntactic complexity of bifix-free languages
• Complexity of suffix-free regular languages
• Complexity of suffix-free regular languages
• Syntactic complexity of suffix-free languages
• Complexity of right-ideal, prefix-closed, and prefix-free regular languages

Cites work

• scientific article; zbMATH DE number 50943 (Why is no real title available?)
• scientific article; zbMATH DE number 3255742 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Classical finite transformation semigroups. An introduction.
• Forests of labeled trees
• Implementation and Application of Automata
• Linear Automaton Transformations
• On deterministic finite automata and syntactic monoid size
• Operational state complexity of prefix-free regular languages
• Quotient complexity of bifix-, factor-, and subword-free regular languages
• Quotient complexity of regular languages
• Some remarks on the combinatorics of \(\mathcal{IS}_n\).
• State complexity of basic operations on suffix-free regular languages
• State complexity of regular languages
• Syntactic complexity of ideal and closed languages
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• The Enumeration of Trees by Height and Diameter

Cited in

(22)

• Upper bound on syntactic complexity of suffix-free languages
• Prefix-free subsets of regular languages and descriptional complexity
• Prefix grammars: An alternative characterization of the regular languages
• Syntactic complexity of bifix-free languages
• Syntactic complexity of ideal and closed languages
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• Complexity of suffix-free regular languages
• Complexity of suffix-free regular languages
• Syntactic complexities of some classes of star-free languages
• Quotient complexity of bifix-, factor-, and subword-free regular languages
• 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
• Syntactic complexity of suffix-free languages
• Syntactic complexity of bifix-free regular languages
• scientific article; zbMATH DE number 7315105 (Why is no real title available?)
• Syntactic complexity of regular ideals
• Descriptional complexity of regular languages
• Complexity of bifix-free regular languages
• Complexity of bifix-free regular languages
• Syntactic complexities of six classes of star-free languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages

Describes a project that uses

Uses Software

• GAP

This page was built for publication: Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages

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