Complexity in convex languages

DOI10.1007/978-3-642-13089-2_1MaRDI QIDQ3564845zbMATH OpenOpenAlexFDO

Authors Janusz Brzozowski

Publication date 26 May 2010

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13089-2_1

zbMATH Keywords

complexityfreeautomatonquotientboundidealconvexlanguageclosedregularstate complexitydecision problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Complexity of proper prefix-convex regular languages
• Complexity of proper prefix-convex regular languages
• Languages convex with respect to binary relations, and their closure properties
• Decision Problems for Convex Languages
• Complexity of right-ideal, prefix-closed, and prefix-free regular languages

Cited in

(14)

• Complexity of proper prefix-convex regular languages
• Convex polyominoes and algebraic languages
• Decision problems for convex languages
• Complexity of proper suffix-convex regular languages
• Power, positive closure, and quotients on convex languages
• Languages convex with respect to binary relations, and their closure properties
• Nondeterministic complexity of operations on free and convex languages
• Nondeterministic complexity in subclasses of convex languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Complexity of proper prefix-convex regular languages
• Complexity of right-ideal, prefix-closed, and prefix-free regular languages
• Incomplete operational transition complexity of regular languages
• Complexity of suffix-free regular languages
• Decision Problems for Convex Languages

This page was built for publication: Complexity in convex languages

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