Nondeterministic state complexity of star-free languages (Q442152): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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)]. The 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. | |||
Property / review text: 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)]. The 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Giovanni Pighizzini / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q19 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6064529 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
star-free languages | |||
Property / zbMATH Keywords: star-free languages / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
nondeterministic finite automata | |||
Property / zbMATH Keywords: nondeterministic finite automata / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
operational state complexity | |||
Property / zbMATH Keywords: operational state complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
descriptional complexity | |||
Property / zbMATH Keywords: descriptional complexity / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.028 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2071992537 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Intersection and union of regular languages and state complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Determination of finite automata accepting subregular languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Roots of Star Events / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2819381 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Decompositions of Regular Events / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5740416 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Quotient complexity of closed languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5740417 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite automata and unary languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A lower bound technique for the size of nondeterministic finite automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4964025 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4964015 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4412108 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3102144 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Descriptional and computational complexity of finite automata -- a survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: State complexity of some operations on binary regular languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4964027 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity in Union-Free Regular Languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5554980 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5641083 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4503152 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal Simulations between Unary Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5541339 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4390537 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On finite monoids having only trivial subgroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4057601 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Power-separating regular languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2731279 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 13:42, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nondeterministic state complexity of star-free languages |
scientific article |
Statements
Nondeterministic state complexity of star-free languages (English)
0 references
9 August 2012
0 references
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)]. The 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.
0 references
star-free languages
0 references
nondeterministic finite automata
0 references
operational state complexity
0 references
descriptional complexity
0 references
0 references
0 references