Syntactic complexity of suffix-free languages

DOI10.1016/J.IC.2017.08.014zbMATH Open1390.68380OpenAlexW2962729556MaRDI QIDQ1706151FDOQ1706151

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

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

zbMATH Keywords

regular languageupper boundtransition semigroupsuffix-freesyntactic complexity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• On nonpermutational transformation semigroups with an application to syntactic complexity
• On syntactic complexity of circular semi-flower automata
• Title not available (Why is that?)
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Upper bounds on syntactic complexity of left and two-sided ideals
• Upper bound on syntactic complexity of suffix-free languages
• The syntactic complexity of semi-flower languages
• Syntactic complexity of bifix-free regular languages
• Syntactic complexity of bifix-free languages

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)