Nondeterministic complexity of operations on free and convex languages

DOI10.1007/978-3-319-60134-2_12MaRDI QIDQ2399254zbMATH OpenOpenAlexFDO

Authors Michal Hospodár, Galina Jirásková, Peter Mlynárčik

Publication date 22 August 2017

Full work available at URL https://doi.org/10.1007/978-3-319-60134-2_12

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Nondeterministic complexity in subclasses of convex languages
• Nondeterministic state complexity for suffix-free regular languages
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Nondeterministic complexity of operations on closed and ideal languages
• Complement on free and ideal languages

Cites work

• Complement on free and ideal languages
• Complement on prefix-free, suffix-free, and non-returning NFA languages
• Complexity in convex languages
• Complexity in union-free regular languages
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• Nondeterministic complexity of operations on closed and ideal languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Quotient complexity of bifix-, factor-, and subword-free regular languages
• Quotient complexity of ideal languages
• State complexity of some operations on binary regular languages

Cited in

(10)

• Power, positive closure, and quotients on convex languages
• Descriptional complexity of power and positive closure on convex languages
• Nondeterministic complexity in subclasses of convex languages
• Nondeterministic complexity of operations on closed and ideal languages
• Decision Problems for Convex Languages
• Nondeterministic state complexity for suffix-free regular languages
• Nondeterministic state complexity of star-free languages
• Complement on free and ideal languages
• Decision problems for convex languages
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity

This page was built for publication: Nondeterministic complexity of operations on free and convex languages

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