Complexity of suffix-free regular languages

DOI10.1007/978-3-319-22177-9_12MaRDI QIDQ2947876zbMATH OpenOpenAlexFDO

Authors Marek Szykuła, Janusz Brzozowski

Publication date 29 September 2015

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

regular languagetransition semigroupstate complexitysuffix-freesyntactic complexitymost complex

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Complexity of suffix-free regular languages
• In search of most complex regular languages
• State Complexity of Basic Operations on Suffix-Free Regular Languages
• State complexity of basic operations on suffix-free regular languages
• Complexity of bifix-free regular languages

Cites work

• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3241282 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• Complexity of suffix-free regular languages
• In search of most complex regular languages
• Languages convex with respect to binary relations, and their closure properties
• Most Complex Regular Right-Ideal Languages
• Quotient complexities of atoms in regular ideal languages
• Quotient complexity of bifix-, factor-, and subword-free regular languages
• Quotient complexity of regular languages
• State complexity of basic operations on suffix-free regular languages
• State complexity of regular languages
• Succinct representation of regular languages by Boolean automata
• Syntactic complexity of ideal and closed languages
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• The state complexities of some basic operations on regular languages
• Theory of átomata
• Upper bound on syntactic complexity of suffix-free languages

Cited in

(19)

• The complexity of regular(-like) expressions
• Complexity in Union-Free Regular Languages
• Theoretical Aspects of Computing – ICTAC 2005
• Complexity of proper suffix-convex regular languages
• scientific article; zbMATH DE number 7315105 (Why is no real title available?)
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Complexity of bifix-free regular languages
• Complexity of bifix-free regular languages
• Overlap-Free Regular Languages
• scientific article; zbMATH DE number 4049104 (Why is no real title available?)
• In search of most complex regular languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Syntactic complexity of suffix-free languages
• Linear-time suffix parsing for deterministic languages
• Complexity of atoms, combinatorially
• Syntactic complexity of bifix-free regular languages
• Complexity of suffix-free regular languages
• Complexity of suffix-free regular languages
• Complexity in union-free regular languages

This page was built for publication: Complexity of suffix-free regular languages

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