Upper Bound on Syntactic Complexity of Suffix-Free Languages

DOI10.1007/978-3-319-19225-3_3zbMath1390.68381arXiv1412.2281OpenAlexW1175148409MaRDI QIDQ5500677

Marek Szykuła, Janusz A. Brzozowski

Publication date: 7 August 2015

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

Full work available at URL: https://arxiv.org/abs/1412.2281

zbMATH Keywords

upper boundregular languagetransition semigroupsuffix-freesyntactic complexity

Mathematics Subject Classification ID

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

Related Items (9)

Syntactic complexity of bifix-free languages ⋮ Complexity of suffix-free regular languages ⋮ Complexity of Suffix-Free Regular Languages ⋮ Syntactic complexity of suffix-free languages ⋮ Syntactic complexity of regular ideals ⋮ Completely Reachable Automata ⋮ Syntactic complexity of bifix-free regular languages ⋮ Descriptional complexity of regular languages ⋮ Upper Bound on Syntactic Complexity of Suffix-Free Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Classical finite transformation semigroups. An introduction.
• State complexity of basic operations on suffix-free regular languages
• Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
• Syntactic Complexity of Ideal and Closed Languages
• Upper Bound on Syntactic Complexity of Suffix-Free Languages

This page was built for publication: Upper Bound on Syntactic Complexity of Suffix-Free Languages