Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
From MaRDI portal
Publication:443735
DOI10.1016/j.tcs.2012.04.011zbMath1280.68108MaRDI 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
semigroup; regular language; finite automaton; monoid; reversal; bifix-free; factor-free; prefix-free; suffix-free; syntactic complexity
Related Items
SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES, Upper Bound on Syntactic Complexity of Suffix-Free Languages, Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages, Complexity of bifix-free regular languages, Complexity of bifix-free regular languages, Syntactic complexity of regular ideals, Syntactic complexity of suffix-free languages, Descriptional complexity of regular languages, Syntactic complexity of bifix-free regular languages, Syntactic complexity of bifix-free languages, Complexity of suffix-free regular languages, Complexity of Suffix-Free Regular Languages
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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