Syntactic complexity of suffix-free languages

DOI10.1016/j.ic.2017.08.014zbMath1390.68380OpenAlexW2962729556MaRDI QIDQ1706151

Marek Szykuła, Janusz A. Brzozowski

Publication date: 21 March 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10012/12500

zbMATH Keywords

upper boundregular languagetransition semigroupsuffix-freesyntactic complexity

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Decision problems for convex languages
• On deterministic finite automata and syntactic monoid size
• Classical finite transformation semigroups. An introduction.
• State complexity of basic operations on suffix-free regular languages
• Complexity of suffix-free regular languages
• Generating Small Automata and the Černý Conjecture
• Implementation and Application of Automata
• Upper Bound on Syntactic Complexity of Suffix-Free Languages