Star-free Language
   HOME





Star-free Language
In theoretical computer science and formal language theory, a regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty word, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star.Lawson (2004) p.235 The condition is equivalent to having generalized star height zero. For instance, the language \Sigma^* of all finite words over an alphabet \Sigma can be shown to be star-free by taking the complement of the empty set, \Sigma^*=\bar. Then, the language of words over the alphabet \ that do not have consecutive a's can be defined as \overline, first constructing the language of words consisting of aa with an arbitrary prefix and suffix, and then taking its complement, which must be all words which do not contain the substring aa. An example of a regular language which is not star-free is (aa)^*, i.e. the language of strings consist ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Theoretical Computer Science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Association for Computing Machinery, ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description: History While logical inference and mathematical proof had existed previously, in 1931 Kurt Gödel proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved. Information theory was added to the field with A Mathematical Theory of Communication, a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of Hebbian learning, learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of neural networks and para ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Marcel-Paul Schützenberger
Marcel-Paul "Marco" Schützenberger (24 October 1920 – 29 July 1996) was a French mathematician and Doctor of Medicine. He worked in the fields of formal language, combinatorics, and information theory.Herbert Wilf, Dominique Foata, ''et al.'',In Memoriam: Marcel-Paul Schützenberger, 1920-1996," ''Electronic Journal of Combinatorics'', served from University of Pennsylvania Dept. of Mathematics Server, article dated 12 October 1996, retrieved from WWW on 4 November 2006. In addition to his formal results in mathematics, he was "deeply involved in struggle against the votaries of eo-arwinism",Foata, Dominique, "In Memoriam," ''op. cit.'' a stance which has resulted in some mixed reactions from his peers and from critics of his stance on evolution. Several notable theorems and objects in mathematics as well as computer science bear his name (for example Schutzenberger group or the Chomsky–Schützenberger hierarchy). Paul Schützenberger was his great-grandfather. In the ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Logic In Computer Science
Logic in computer science covers the overlap between the field of logic and that of computer science. The topic can essentially be divided into three main areas: * Theoretical foundations and analysis * Use of computer technology to aid logicians * Use of concepts from logic for computer applications Theoretical foundations and analysis Logic plays a fundamental role in computer science. Some of the key areas of logic that are particularly significant are computability theory (formerly called recursion theory), modal logic and category theory. The theory of computation is based on concepts defined by logicians and mathematicians such as Alonzo Church and Alan Turing. Church first showed the existence of Undecidable problem, algorithmically unsolvable problems using his notion of lambda-definability. Turing gave the first compelling analysis of what can be called a mechanical procedure and Kurt Gödel asserted that he found Turing's analysis "perfect.". In addition some other ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Generalized Star-height Problem
The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but they have a built-in complement operator. For a regular language, its generalized star height is defined as the minimum nesting depth of Kleene stars needed in order to describe the language by means of a generalized regular expression, hence the name of the problem. More specifically, it is an open question whether a nesting depth of more than 1 is required, and if so, whether there is an algorithm to determine the minimum required star height.Sakarovitch (2009) p.171 Regular languages of star-height 0 are also known as star-free languages. The theorem of Schützenberger provides an algebraic characterization of star-free languages by means of aperiodic syntactic monoids. In particular s ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Star Height Problem
The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required? The problem was first introduced by Eggan in 1963. Families of regular languages with unbounded star height The first question was answered in the negative when in 1963, Eggan gave examples of regular languages of star height ''n'' for every ''n''. Here, the star height ''h''(''L'') of a regular language ''L'' is defined as the minimum star height among all regular expressions representing ''L''. The first few languages found by Eggan are described in the following, by means of giving a regular expression for each language: :\begin e_1 &= a_1^* \\ e_2 &= \left(a_1^*a_2^*a_3\right)^*\\ e_3 &= \left(\left(a_1^*a_2^*a_3\right)^*\left(a_4^*a_5^*a_6\r ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Star Height
In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions and regular languages. The star height of a regular ''expression'' equals the maximum nesting depth of stars appearing in that expression. The star height of a regular ''language'' is the least star height of any regular expression for that language. The concept of star height was first defined and studied by Eggan (1963). Formal definition More formally, the star height of a regular expression ''E'' over a finite alphabet ''A'' is inductively defined as follows: * \textstyle h\left(\emptyset\right)\,=\,0, \textstyle h\left(\varepsilon\right)\,=\,0, and \textstyle h\left(a\right)\,=\,0 for all alphabet symbols ''a'' in ''A''. * \textstyle h\left(E F\right)\,=\, h\left(E\, \mid\, F\right)\,=\,\max \left(\, h(E), h(F)\,\right) * \textstyle h\left(E^*\right)\,=\,h(E)+1. Here, \scriptstyle \emptyset is the special regular ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Linear Temporal Logic
In logic, linear temporal logic or linear-time temporal logic (LTL) is a modal logic, modal temporal logic with modalities referring to time. In LTL, one can encode formula (logic), formulae about the future of path (graph theory), paths, e.g., a condition will eventually be true, a condition will be true until another fact becomes true, etc. It is a fragment of the more complex CTL*, which additionally allows branching time and quantifier (logic), quantifiers. LTL is sometimes called propositional temporal logic (PTL). In terms of expressive power (computer science), expressive power, LTL is a fragment of first-order logic. LTL was first proposed for the formal verification of computer programs by Amir Pnueli in 1977. Syntax LTL is built up from a finite set of propositional variables ''AP'', the logical connective, logical operators ¬ and ∨, and the Temporal logic, temporal modal operators X (some literature uses O or N) and U. Formally, the set of LTL formulas over ''AP'' is ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Aperiodic Finite-state Automaton
An aperiodic finite-state automaton (also called a counter-free automaton) is a finite-state automaton whose transition monoid is aperiodic. Properties A regular language is star-free if and only if it is accepted by an automaton with a finite and aperiodic transition monoid. This result of algebraic automata theory is due to Marcel-Paul Schützenberger. In particular, the minimum automaton of a star-free language is always counter-free (however, a star-free language may also be recognized by other automata that are not aperiodic). A counter-free language is a regular language for which there is an integer ''n'' such that for all words ''x'', ''y'', ''z'' and integers ''m'' ≥ ''n'' we have ''xy''''m''''z'' in ''L'' if and only if ''xy''''n''''z'' in ''L''. For these languages, when a string contains enough repetitions of any substring (at least ''n'' repetitions), changing the number of repetitions to another number that is at least ''n'' cannot change membership in the language ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

First-order Logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables. Rather than propositions such as "all humans are mortal", in first-order logic one can have expressions in the form "for all ''x'', if ''x'' is a human, then ''x'' is mortal", where "for all ''x"'' is a quantifier, ''x'' is a variable, and "... ''is a human''" and "... ''is mortal''" are predicates. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic. A theory about a topic, such as set theory, a theory for groups,A. Tarski, ''Undecidable Theories'' (1953), p. 77. Studies in Logic and the Foundation of Mathematics, North-Holland or a formal theory o ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Syntactic Monoid
In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the minimal monoid that recognizes the language L. By the Myhill–Nerode theorem, the syntactic monoid is unique up to unique isomorphism. Syntactic quotient An alphabet is a finite set. The free monoid on a given alphabet is the monoid whose elements are all the strings of zero or more elements from that set, with string concatenation as the monoid operation and the empty string as the identity element. Given a subset S of a free monoid M, one may define sets that consist of formal left or right inverses of elements in S. These are called quotients, and one may define right or left quotients, depending on which side one is concatenating. Thus, the right quotient of S by an element m from M is the set :S \ / \ m=\. Similarly, the left quotient is :m \setminus S=\. Syntactic equivalence The syntactic quotient induces an equivalence relation on M, called the syntactic relation, o ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Aperiodic Monoid
In mathematics, an aperiodic semigroup is a semigroup ''S'' such that every element is aperiodic, that is, for each ''x'' in ''S'' there exists a positive integer ''n'' such that ''xn'' = ''x''''n''+1. An aperiodic monoid is an aperiodic semigroup which is a monoid. Finite aperiodic semigroups A finite semigroup is aperiodic if and only if it contains no nontrivial subgroups, so a synonym used (only?) in such contexts is group-free semigroup. In terms of Green's relations, a finite semigroup is aperiodic if and only if its ''H''-relation is trivial. These two characterizations extend to group-bound semigroups. A celebrated result of algebraic automata theory due to Marcel-Paul Schützenberger asserts that a language is Star-free language, star-free if and only if its syntactic monoid is finite and aperiodic.Schützenberger, Marcel-Paul, "On finite monoids having only trivial subgroups," ''Information and Control'', Vol 8 No. 2, pp. 190–194, 1965. A consequence of the Krohn–R ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Generalized Star Height
In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions and regular languages. The star height of a regular ''expression'' equals the maximum nesting depth of stars appearing in that expression. The star height of a regular ''language'' is the least star height of any regular expression for that language. The concept of star height was first defined and studied by Eggan (1963). Formal definition More formally, the star height of a regular expression ''E'' over a finite alphabet ''A'' is inductively defined as follows: * \textstyle h\left(\emptyset\right)\,=\,0, \textstyle h\left(\varepsilon\right)\,=\,0, and \textstyle h\left(a\right)\,=\,0 for all alphabet symbols ''a'' in ''A''. * \textstyle h\left(E F\right)\,=\, h\left(E\, \mid\, F\right)\,=\,\max \left(\, h(E), h(F)\,\right) * \textstyle h\left(E^*\right)\,=\,h(E)+1. Here, \scriptstyle \emptyset is the special regular ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]