Nondeterministic complexity in subclasses of convex languages
From MaRDI portal
Publication:2319915
DOI10.1016/j.tcs.2018.12.027zbMath1429.68118OpenAlexW2908422417WikidataQ128638117 ScholiaQ128638117MaRDI QIDQ2319915
Galina Jirásková, Michal Hospodár, Peter Mlynárčik
Publication date: 20 August 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.12.027
complementationKleene starintersectiondescriptional complexityunionconcatenationreversalnondeterministic finite automataoperational state complexityclosed languagesconvex languagesideal languagesfree languages
Related Items (5)
Nondeterministic operational complexity in subregular languages ⋮ The cut operation in subclasses of convex languages ⋮ Power, positive closure, and quotients on convex languages ⋮ Closure properties of subregular languages under operations ⋮ Operations on subregular languages and nondeterministic state complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nondeterministic state complexity of star-free languages
- A lower bound technique for the size of nondeterministic finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Unary finite automata vs. arithmetic progressions
- On NFAs where all states are final, initial, or both
- Intersection and union of regular languages and state complexity
- The state complexities of some basic operations on regular languages
- Quotient complexity of closed languages
- State complexity of some operations on binary regular languages
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Quotient complexity of ideal 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
- Nondeterministic complexity of operations on free and convex languages
- Nondeterministic Complexity of Operations on Closed and Ideal Languages
- COMPLEXITY IN UNION-FREE REGULAR LANGUAGES
- State complexity of cyclic shift
- Complexity in Convex Languages
- Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
- QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
- Quotient Complexity of Bifix-, Factor-, and Subword-free Regular Language
- Nondeterminism and the size of two way finite automata
- Complement on Prefix-Free, Suffix-Free, and Non-Returning NFA Languages
- Complement on Free and Ideal Languages
- On free monoids partially ordered by embedding
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Complexity of proper prefix-convex regular languages
- A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
This page was built for publication: Nondeterministic complexity in subclasses of convex languages
