Upper Bound on Syntactic Complexity of Suffix-Free Languages

DOI10.1007/978-3-319-19225-3_3zbMath1390.68381arXiv1412.2281MaRDI 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 bound; regular language; transition semigroup; suffix-free; syntactic complexity

Mathematics Subject Classification ID

68Q45: Formal languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Upper Bound on Syntactic Complexity of Suffix-Free 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, Completely Reachable Automata, Complexity of Suffix-Free Regular 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