formulasearchengine - User contributions [en]

D'Alembert's paradox

2014-11-02T06:55:42Z

50.30.193.214:

Hi there! :) My name is Flossie, I'm a student studying Environmental Management from Bremen Woltmershausen, Germany. my webpage [http://michaldymi.livejournal.com water damage restoration]

Bombieri–Vinogradov theorem

2013-10-16T04:38:14Z

50.30.141.251: /* Statement of the Bombieri–Vinogradov theorem */

A '''matrix grammar''' is a [[formal grammar]] in which instead of single productions, productions are grouped together into finite sequences. A production cannot be applied separately, it must be applied in sequence. In the application of such a sequence of productions, the rewriting is done in accordance to the each production in sequence, the first one, second one etc. till the last production has been used for rewriting. The sequences are referred to as '''matrices'''.

Matrix grammar is an extension of [[context-free grammar]], and one instance of a [[Controlled grammar]].

== Formal definition ==
A ''matrix grammar'' is an ordered quadruple

:<math>G = (V_N, V_T, X_0, M).</math>

where

* <math>V_N</math> is a finite set of non-terminals
* <math>V_T</math> is a finite set of terminals
* <math>X_0</math> is a special element of <math>V_N</math>, viz. the starting symbol
* <math>M</math> is a finite set of non-empty sequences whose elements are ordered pairs

:<math>(P, Q), \quad P \in W(V) V_N W(V), \quad Q \in W(V), \quad V = V_N \cup V_T.</math>

The pairs are called productions, written as <math>P \to Q</math>. The sequences are called matrices and can be written as

:<math>m = [P_1 \to Q_1, \ldots, P_r \to Q_r].</math>

Let <math>F</math> be the set of all productions appearing in the matrices <math>m</math> of a matrix grammar <math>G</math>. Then the matrix grammar <math>G</math> is of type-<math>i, i = 0, 1, 2, 3</math>, ''length-increasing'', ''linear'', ''<math>\lambda</math>-free'', ''context-free'' or ''context-sensitive'' if and only if the grammar <math>G_1 = (V_N, V_T, X_0, F)</math> has the following property.

For a matrix grammar <math>G</math>, a binary relation <math>\Rightarrow_G</math> is defined; also represented as <math>\Rightarrow</math>. For any <math>P, Q \in W(V)</math>, <math>P \Rightarrow Q</math> holds if and only if there exists an integer <math>r \ge 1</math> such that the words

:<math>\alpha_1,, \ldots, \alpha_{r + 1}, \quad P_1, \ldots, P_r, \quad R_1, \ldots, R_r, \quad, R^1, \ldots, R^r</math>

over V exist and

* <math>\alpha_i = P</math> and <math>\alpha_{r + 1} = Q</math>
* <math>m</math> is one of the matrices of <math>G</math>
* <math>\alpha_i = R_i P_i R^i</math> and <math>\alpha_{i + 1} = R_i Q_i R^i.</math>

If the above conditions are satisfied, it is also said that <math>P \Rightarrow Q</math> holds with <math>(m, R_1)</math> as the ''specifications''.

Let <math>\Rightarrow^{*}</math> be the reflexive transitive closure of the relation <math>\Rightarrow</math>. Then, the language generated by the matrix grammar <math>G</math> is given by

:<math>L(G) = \{P \in W(V_T) | X_0 \Rightarrow^{*} P\}.</math>

== Example ==

Consider the matrix grammar

<math>G = (\{S, X, Y\}, \{a, b, c\}, S, M)</math>

where <math>M</math> is a collection containing the following matrices:

<math>[S \rightarrow XY], \quad [X \rightarrow aXb, Y \rightarrow cY], \quad [X \rightarrow ab, Y \rightarrow c]</math>

These matrices, which contain only ''context-free'' rules generate the ''context-sensitive'' language

<math>L = \{a^nb^nc^n|n \ge 1\}.</math>

This example can be found on pages 8 and 9 of {{ref|Abraham1965}}.

== Properties ==

Let <math>MAT^\lambda</math> be the class of languages produced by matrix grammars, and <math>MAT</math> the class of languages produced by <math>\lambda</math>-free matrix grammars.

* Trivially, <math>MAT</math> is included in <math>MAT^\lambda</math>.
* All [[context-free languages]] are in <math>MAT</math>, and all languages in <math>MAT^\lambda</math> are [[recursively enumerable]].
* <math>MAT</math> is closed under [[Union (set theory)|union]], [[concatenation]], [[Intersection (set theory)|intersection]] with regular languages and permutation.
* All languages in <math>MAT</math> can be produced by a [[context-sensitive grammar]].
* There exists some languages in <math>MAT^\lambda</math> which can not be produced by a context-sensitive grammar.
* Each language produced by a matrix grammar with only one terminal symbol is regular.

== Open problems ==

It is not known whether there exist languages in <math>MAT^\lambda</math> which are not in <math>MAT</math>, and it is neither known whether <math>MAT^\lambda</math> contains languages which are not context-sensitive {{ref|Paun}}.

== References ==
* {{note|Abraham1965}} Ábrahám, S. Some questions of language theory. International Conference on Computational Linguistic, 1965. pp 1-11. [http://acl.ldc.upenn.edu/C/C65/C65-1001.pdf]
* {{note|Paun}} Gheorghe Păun, Membrane Computing: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002. pp 30-32

[[Category:Formal languages]]

Taylor KO Factor

2013-01-27T03:42:07Z

50.30.192.115: /* Alternative Approaches */ Corrected a cartridge name reference

In [[set theory]], the '''singular cardinals hypothesis (SCH)''' arose from the question of whether the least [[cardinal number]] for which the [[Continuum hypothesis#The generalized continuum hypothesis|generalized continuum hypothesis]] (GCH) might fail could be a [[singular cardinal]].

According to Mitchell (1992), the singular cardinals hypothesis is:
:If κ is any singular [[limit cardinal|strong limit cardinal]], then 2κ = κ+.
Here, κ+ denotes the [[successor cardinal]] of κ.

Since SCH is a consequence of GCH which is known to be [[consistent]] with [[Zermelo–Fraenkel set theory|ZFC]], SCH is consistent with ZFC. The negation of SCH has also been shown to be consistent with ZFC, if one assumes the existence of a sufficiently large cardinal number. In fact, by results of [[Moti Gitik]], ZFC + the negation of SCH is equiconsistent with ZFC + the existence of a measurable cardinal κ of [[Mitchell order]] κ++.

Another form of the SCH is the following statement:
:2cf(κ) < κ implies κcf(κ) = κ+,
where cf denotes the [[cofinality]] function. Note that κcf(κ)= 2κ for all singular strong limit cardinals κ. The second formulation of SCH is strictly stronger than the first version, since the first one only mentions strong limits; from a model in which the first version of SCH fails at &alefsym;ω and GCH holds above &alefsym;ω+2, we can construct a model in which the first version of SCH holds but the second version of SCH fails, by adding &alefsym;ω Cohen subsets to &alefsym;n for some n.

[[Jack Silver|Silver]] proved that if κ is singular with uncountable cofinality and 2λ = λ+ for all infinite cardinals λ < κ, then 2κ = κ+. Silver's original proof used [[generic ultrapowers]]. The following important fact follows from Silver's theorem: if the singular cardinals hypothesis holds for all singular cardinals of countable cofinality, then it holds for all singular cardinals. In particular, then, if <math> \kappa </math> is the least counterexample to the singular cardinals hypothesis, then <math> cf(\kappa) = \omega </math>.

The negation of the singular cardinals hypothesis is intimately related to violating the GCH at a measurable cardinal. A well-known result of [[Dana Scott]] is that if the GCH holds below a measurable cardinal <math> \kappa </math> on a set of measure one—i.e., there is normal <math> \kappa </math> -complete ultrafilter D on <math> \mathcal{P}(\kappa) </math> such that <math> \{\alpha < \kappa: 2^{\alpha} = \alpha^+\}\in D </math>, then <math> 2^\kappa = \kappa^+ </math>. Starting with <math> \kappa </math> a [[supercompact cardinal]], Silver was able to produce a model of set theory in which <math> \kappa </math> is measurable and in which <math> 2^\kappa > \kappa^+ </math>. Then, by applying [[Prikry forcing]] to the measurable <math> \kappa </math>, one gets a model of set theory in which <math> \kappa </math> is a strong limit cardinal of countable cofinality and in which <math> 2^\kappa > \kappa^+ </math>—a violation of the SCH. [[Moti Gitik|Gitik]], building on work of [[W. Hugh Woodin|Woodin]], was able to replace the supercompact in Silver's proof with a measurable of Mitchell order <math> \kappa^{++} </math>. That established an upper bound for the consistency strength of the failure of the SCH. Gitik again, using results of [[Inner model theory]], was able to show that a measurable of Mitchell order <math> \kappa^{++} </math> is also the lower bound for the consistency strength of the failure of SCH.

A wide variety of propositions imply SCH. As was noted above, GCH implies SCH. On the other hand, the [[proper forcing axiom]] which implies <math> 2^{\aleph_0} = \aleph_2 </math> and hence is incompatible with GCH also implies SCH. [[Robert M. Solovay|Solovay]] showed that large cardinals almost imply SCH—in particular, if <math> \kappa </math> is [[strongly compact cardinal]], then the SCH holds above <math> \kappa </math>. On the other hand, the non-existence of (inner models for) various large cardinals (below a measurable of Mitchell order <math> \kappa^{++} </math>) also imply SCH.

==References==
* [[Thomas Jech|T. Jech]]: [http://matwbn.icm.edu.pl/ksiazki/fm/fm81/fm8116.pdf Properties of the gimel function and a classification of singular cardinals], ''[[Fundamenta Mathematicae]]'', '''81'''(1974), 57-64.
* William J. Mitchell, "On the singular cardinal hypothesis," ''Trans. Amer. Math. Soc.'', volume 329, number 2, pages 507–530, 1992.
* Jason Aubrey, ''The Singular Cardinals Problem'' ([http://www.math.lsa.umich.edu/vigre/Expositions/Aubrey.pdf PDF]), VIGRE expository report, Department of Mathematics, University of Michigan.

[[Category:Cardinal numbers]]