Complexity of proper prefix-convex regular languages

DOI10.1007/978-3-319-60134-2_5MaRDI QIDQ5920052zbMATH OpenOpenAlexFDO

Authors Janusz Brzozowski, Corwin W. Sinnamon

Publication date 22 August 2017

Published in Implementation and Application of Automata (Search for Journal in Brave)

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

zbMATH Keywords

atommost complexprefix-convexproperquotient complexityregular languagestate complexitysyntactic semigroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Complexity of proper prefix-convex regular languages
• Complexity of right-ideal, prefix-closed, and prefix-free regular languages
• Complexity in convex languages
• Complexity of proper suffix-convex regular languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages

Cites work

• Codes and automata.
• Complexity of atoms, combinatorially
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Complexity of right-ideal, prefix-closed, and prefix-free regular languages
• scientific article; zbMATH DE number 3416974 (Why is no real title available?)
• Implementation and Application of Automata
• In search of most complex regular languages
• Languages convex with respect to binary relations, and their closure properties
• Most complex regular ideal languages
• On deterministic finite automata and syntactic monoid size
• Quotient complexity of regular languages
• State complexity of regular languages
• Syntactic complexity of ideal and closed languages
• The state complexities of some basic operations on regular languages
• Theory of átomata

Cited in

(16)

• Complexity of proper suffix-convex regular languages
• Nondeterministic complexity in subclasses of convex languages
• scientific article; zbMATH DE number 3843156 (Why is no real title available?)
• Complexity in convex languages
• Decision Problems for Convex Languages
• scientific article; zbMATH DE number 4078833 (Why is no real title available?)
• Convex and anti-convex languages
• scientific article; zbMATH DE number 7315105 (Why is no real title available?)
• scientific article; zbMATH DE number 7503138 (Why is no real title available?)
• Languages convex with respect to binary relations, and their closure properties
• Complexity of right-ideal, prefix-closed, and prefix-free regular languages
• Decision problems for convex languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Complexity of proper prefix-convex regular languages
• Complexity of bifix-free regular languages
• Complexity of bifix-free regular languages

This page was built for publication: Complexity of proper prefix-convex regular languages

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