Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages

DOI10.1007/978-3-642-22600-7_8zbMath1341.68080OpenAlexW272675MaRDI QIDQ5200084

Yuli Ye, Baiyu Li, Janusz A. Brzozowski

Publication date: 29 July 2011

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_8

zbMATH Keywords

semigroupregular languagefinite automatonmonoidsyntactic complexityprefix-free languagebifix-free languagesuffix-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (1)

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

Uses Software

• GAP

Cites Work

• 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
• Linear Automaton Transformations
• Syntactic Complexity of Ideal and Closed Languages

This page was built for publication: Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages