Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
From MaRDI portal
Publication:443735
DOI10.1016/J.TCS.2012.04.011zbMATH Open1280.68108OpenAlexW1978707564MaRDI QIDQ443735FDOQ443735
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
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
regular languagesemigroupmonoidfinite automatonreversalbifix-freefactor-freeprefix-freesuffix-freesyntactic complexity
Cites Work
- State complexity of regular languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Classical finite transformation semigroups. An introduction.
- Quotient complexity of bifix-, factor-, and subword-free regular languages
- Operational state complexity of prefix-free regular languages
- State complexity of basic operations on suffix-free regular languages
- Title not available (Why is that?)
- Some remarks on the combinatorics of \(\mathcal{IS}_n\).
- Quotient complexity of regular languages
- Linear Automaton Transformations
- The Enumeration of Trees by Height and Diameter
- Syntactic complexity of ideal and closed languages
- Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
- Implementation and Application of Automata
- Forests of labeled trees
- Title not available (Why is that?)
- On deterministic finite automata and syntactic monoid size
Cited In (22)
- 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
- Prefix-free subsets of regular languages and descriptional complexity
- Title not available (Why is that?)
- Syntactic complexity of regular ideals
- Complexity of bifix-free regular languages
- Complexity of bifix-free regular languages
- Upper bound on syntactic complexity of suffix-free languages
- Complexity of left-ideal, suffix-closed and suffix-free regular languages
- Syntactic complexity of suffix-free languages
- Prefix grammars: An alternative characterization of the regular languages
- Syntactic complexity of ideal and closed languages
- Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
- Syntactic complexities of some classes of star-free languages
- Syntactic complexities of six classes of star-free languages
- Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages
- Syntactic complexity of bifix-free regular languages
- Descriptional complexity of regular languages
- Syntactic complexity of bifix-free languages
- Complexity of suffix-free regular languages
- Complexity of suffix-free regular languages
Uses Software
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)
