Nondeterministic complexity in subclasses of convex languages
From MaRDI portal
Recommendations
- Nondeterministic complexity of operations on free and convex languages
- Complexity in convex languages
- Nondeterministic operational complexity in subregular languages
- Nondeterministic complexity of operations on closed and ideal languages
- Descriptional complexity of power and positive closure on convex languages
- Complexity of certain decision problems about congruential languages
- Convex language semantics for nondeterministic probabilistic automata
- Nonuniform complexity and the randomness of certain complete languages
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Random languages for nonuniform complexity classes
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 1156489 (Why is no real title available?)
- scientific article; zbMATH DE number 2050931 (Why is no real title available?)
- scientific article; zbMATH DE number 2068872 (Why is no real title available?)
- scientific article; zbMATH DE number 2068876 (Why is no real title available?)
- scientific article; zbMATH DE number 2182451 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 1916664 (Why is no real title available?)
- scientific article; zbMATH DE number 918133 (Why is no real title available?)
- scientific article; zbMATH DE number 7315105 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3305062 (Why is no real title available?)
- scientific article; zbMATH DE number 3353192 (Why is no real title available?)
- A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
- A lower bound technique for the size of nondeterministic finite automata
- A survey on operational state complexity
- 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
- Complexity of proper prefix-convex regular languages
- Determination of finite automata accepting subregular languages
- Implementation and application of automata. 22nd international conference, CIAA 2017, Marne-la-Vallée, France, June 27--30, 2017. Proceedings
- Intersection and union of regular languages and state complexity
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Nondeterminism and the size of two way finite automata
- Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
- Nondeterministic complexity of operations on closed and ideal languages
- Nondeterministic complexity of operations on free and convex languages
- Nondeterministic state complexity for suffix-free regular languages
- Nondeterministic state complexity of star-free languages
- Nonterminal complexity of some operations on context-free languages
- On NFAs where all states are final, initial, or both
- On free monoids partially ordered by embedding
- Operations on automata with all states final
- Partial orders on words, minimal elements of regular languages, and state complexity
- QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
- Quotient complexity of bifix-, factor-, and subword-free regular languages
- Quotient complexity of ideal languages
- State complexity of cyclic shift
- State complexity of some operations on binary regular languages
- The state complexities of some basic operations on regular languages
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Unary finite automata vs. arithmetic progressions
Cited in
(14)- Operations on subregular languages and nondeterministic state complexity
- Decision problems for convex languages
- The cut operation in subclasses of convex languages
- On the relative complexity of some languages in \(NC^ 1\)
- Complement on prefix-free, suffix-free, and non-returning NFA languages
- Complement on free and ideal languages
- Power, positive closure, and quotients on convex languages
- Closure properties of subregular languages under operations
- Descriptional complexity of power and positive closure on convex languages
- Nondeterministic complexity of operations on free and convex languages
- Nondeterministic operational complexity in subregular languages
- Closure properties of subregular languages under operations
- Decision Problems for Convex Languages
- Nondeterministic complexity of operations on closed and ideal languages
This page was built for publication: Nondeterministic complexity in subclasses of convex languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2319915)
