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

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

zbMATH Keywords

semigroup; regular language; finite automaton; monoid; reversal; bifix-free; factor-free; prefix-free; suffix-free; syntactic complexity

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q19: Descriptive complexity and finite models

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

• GAP

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