Syntactic complexity of suffix-free languages

DOI10.1016/J.IC.2017.08.014MaRDI QIDQ1706151zbMATH OpenOpenAlexFDO

Authors Marek Szykuła, Janusz 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

regular languageupper boundtransition semigroupsuffix-freesyntactic complexity

Mathematics Subject Classification ID

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

Recommendations

• Upper bound on syntactic complexity of suffix-free languages
• Syntactic complexity of bifix-free languages
• Syntactic complexities of some classes of star-free languages
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• Complexity of suffix-free regular languages
• Complexity of suffix-free regular languages
• scientific article; zbMATH DE number 4028929
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Syntactic complexities of six classes of star-free languages
• Syntactic complexity of bifix-free regular languages

Cites work

• scientific article; zbMATH DE number 3416974 (Why is no real title available?)
• Classical finite transformation semigroups. An introduction.
• Complexity of suffix-free regular languages
• Decision problems for convex languages
• Generating small automata and the Černý conjecture
• Implementation and Application of Automata
• Languages convex with respect to binary relations, and their closure properties
• On deterministic finite automata and syntactic monoid size
• Quotient complexity of regular languages
• State complexity of basic operations on suffix-free regular languages
• State complexity of regular languages
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Upper bound on syntactic complexity of suffix-free languages

Cited in

(9)

• Upper bound on syntactic complexity of suffix-free languages
• scientific article; zbMATH DE number 3854452 (Why is no real title available?)
• Syntactic complexity of bifix-free languages
• The syntactic complexity of semi-flower languages
• On syntactic complexity of circular semi-flower automata
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Syntactic complexity of bifix-free regular languages
• On nonpermutational transformation semigroups with an application to syntactic complexity
• Upper bounds on syntactic complexity of left and two-sided ideals

This page was built for publication: Syntactic complexity of suffix-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1706151)