Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
From MaRDI portal
Publication:443735
DOI10.1016/J.TCS.2012.04.011zbMath1280.68108OpenAlexW1978707564MaRDI QIDQ443735
Baiyu Li, Yuli Ye, Janusz A. 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
semigroupregular languagefinite automatonmonoidreversalbifix-freefactor-freeprefix-freesuffix-freesyntactic complexity
Related Items (12)
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 Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages ⋮ SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES ⋮ Syntactic complexity of regular ideals ⋮ Complexity of bifix-free regular languages ⋮ Complexity of bifix-free regular languages ⋮ Syntactic complexity of bifix-free regular languages ⋮ Descriptional complexity of regular languages ⋮ Upper Bound on Syntactic Complexity of Suffix-Free Languages
Uses Software
Cites Work
- On deterministic finite automata and syntactic monoid size
- Classical finite transformation semigroups. An introduction.
- State complexity of basic operations on suffix-free regular languages
- Some remarks on the combinatorics of \(\mathcal{IS}_n\).
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
