Nondeterministic state complexity of star-free languages
The class of star-free languages is a relevant subclass of regular languages, which can be described in terms of regular expressions, extended to include all boolean operators, but without Kleene star. Properties of this class have been widely investigated in the literature. In particular, concerning \textit{descriptional complexity}, the field of investigation where this paper can be classified, a recent interesting result shows that the exponential state gap between nondeterministic and deterministic finite automata can be achieved even restricting to star-free languages [\textit{H. Bordihn}, \textit{M. Holzer} and \textit{M. Kutrib}, Theor.\ Comput.\ Sci.\ 410, No. 35, 3209--3222 (2009; Zbl 1173.68030)].NEWLINENEWLINEThe paper investigates the nondeterministic state complexity of the basic operations on star-free languages. A similar investigation for the deterministic case has been done in [\textit{J. Brzozowski} and \textit{B. Liu}, Int.\ J.\ Found.\ Comput.\ Sci.\ 23, No. 6, 1261--1276 (2012; Zbl 1272.68206)]. It is shown that the lowed bounds which are known for those operations on regular languages can be achieved even restricting to star-free languages, namely, the nondeterministic state complexities of those operations remain the same restricting to star-free languages. The case of unary star-free languages, namely, star-free languages defined over a one letter alphabet, is also considered. Only one relevant difference with respect to the general case is discovered: the complementation of unary star-free languages uses a quadratic number of states, while the same operation in the general case requires exponentially many states.
- Nondeterministic state complexity of star-free languages
- QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
- Quotient complexity of star-free languages
- Star-complement-star on prefix-free languages
- Syntactic complexities of six classes of star-free languages
- Square, power, positive closure, and complementation on star-free languages
- Nondeterministic state complexity for suffix-free regular languages
- Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
- Syntactic complexities of some classes of star-free languages
- State complexity of basic operations on suffix-free regular languages
- A lower bound technique for the size of nondeterministic finite automata
- Complexity in Union-Free Regular Languages
- Descriptional and computational complexity of finite automata -- a survey
- Descriptional complexity -- an introductory survey
- Determination of finite automata accepting subregular languages
- Finite automata and unary languages
- scientific article; zbMATH DE number 3473324 (Why is no real title available?)
- scientific article; zbMATH DE number 1156489 (Why is no real title available?)
- scientific article; zbMATH DE number 1948495 (Why is no real title available?)
- scientific article; zbMATH DE number 1502111 (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 3269886 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- Intersection and union of regular languages and state complexity
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Nondeterministic state complexity for suffix-free regular languages
- Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
- On Decompositions of Regular Events
- On finite monoids having only trivial subgroups
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Optimal simulations between unary automata
- Power-separating regular languages
- Quotient complexity of bifix-, factor-, and subword-free regular languages
- Quotient complexity of regular languages
- Quotient complexity of star-free languages
- Roots of Star Events
- State complexity of regular languages
- State complexity of some operations on binary regular languages
- The magic number problem for subregular language families
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- Closure properties of subregular languages under operations
- Operations on subregular languages and nondeterministic state complexity
- Square, power, positive closure, and complementation on star-free languages
- Nondeterminism growth and state complexity
- Nondeterministic complexity in subclasses of convex languages
- Concatenation-free languages
- Expressive capacity of concatenation freeness
- QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
- Nondeterministic state complexity of star-free languages
- Expressive capacity of subregular expressions
- State complexity of unary language operations for NFAs with limited nondeterminism
- Nondeterministic operational complexity in subregular languages
- The nondeterministic state complexity of the site-directed deletion language operation
- Square, power, positive closure, and complementation on ordered and star-free languages
- Closure properties of subregular languages under operations
- Operational state complexity of unary NFAs with finite nondeterminism
This page was built for publication: Nondeterministic state complexity of star-free languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442152)
