en>Wavelength: inserting 1 hyphen: —> "higher-dimensional"—User talk:Wavelength#Hyphenation [to Archive 6]

2014-04-12T01:43:41Z

inserting 1 hyphen: —> "higher-dimensional"—User talk:Wavelength#Hyphenation [to Archive 6]

en>YuriYoghi at 07:04, 27 May 2013

2013-05-27T07:04:29Z

← Older revision		Revision as of 09:04, 27 May 2013
Line 1:		Line 1:
	~~Hello! My~~ name is ~~Alisha~~. ~~I am happy~~ that ~~I can join~~ to the ~~entire world~~. ~~I live~~ in ~~France~~, in the ~~region~~. ~~I dream~~ to ~~check~~ out the ~~different countries~~, to ~~obtain acquainted with fascinating individuals.~~<br><br>~~my web page;~~ [~~http~~://~~www~~.~~olwallpaper~~.~~com~~/~~profile~~/~~vigula Biking~~ for ~~modern life mountain bike sizing.~~]		Global index grammars (GIGs) are a class of grammars introduced in Castaño (2004)<ref name="castano2004">Castaño, José M. 2004. ''Global Index Languages''. Dissertation, Brandeis University.</ref> in order to model a number of phenomena, including natural language grammar and genome grammar. The easiest description of GIGs is by comparison to [[Indexed grammar]]s. Whereas in indexed grammars, a stack of indices is associated with each [[nonterminal symbol]], and can vary from one to another depending on the course of the derivation, in a GIG, there is a single global index stack that is manipulated in the course of the derivation (which is strictly leftmost for any rewrite operation that pushes a symbol to the stack). Because of the existence of a global stack, a GIG derivation is considered complete when there are no non-terminal symbols left to be rewritten, and the stack is empty.

			==Rule Description==

			GIG rules come in essentially four forms: rules that do something unconditionally, rules that do something conditioned on the topmost symbol of the stack, rules that push to the stack, and rules that pop from the stack. We can notate these in turn as:

			{\|
			\|-
			\| <math>A \to \alpha</math>
			\| ''(unconditionally rewrite A as <math>\alpha</math>, doing nothing to the stack)''
			\|-
			\| <math>A \xrightarrow[f]{} \alpha</math>
			\| ''(rewrite A as <math>\alpha</math> if f is the topmost stack symbol, doing nothing to the stack)''
			\|-
			\| <math>A \xrightarrow[+f]{} x \alpha</math>
			\| ''(unconditionally rewrite A as <math>x \alpha</math> and push f to the stack)''
			\|-
			\| <math>A \xrightarrow[-f]{} \alpha</math>
			\| ''(conditionally rewrite A as <math>\alpha</math> if f is the topmost symbol of the stack, then pop f from the stack)''
			\|}

			where f is any index symbol, <math>\alpha</math> is any string of terminals and/or non-terminal symbols, and x is a terminal is a terminal symbol. Because occasionally a rewrite rule might need to be conditioned on the stack being in some sense ''empty'', the symbol ''#'' is used as the bottom-most stack symbol, meaning an "empty" stack contains exactly one symbol, ''#''.

			The third rule form, the push rule, should be pointed out, as it differs from the pop rule in requiring that all push operations introduce at least one new terminal symbol to the derivation string. Without this constraint, the class of grammars would be Type-0 and thus Turing Complete.

			==Example==

			For this example, we will denote steps in the derivation by placing the derivation string over a stack, as in <math>\frac{abXd}{[ffg]}</math>.

			GIGs (but not trGIGs as below) can generate the non-indexed language <math>\{ ww^{+} : w \in \{a,b\}^{*} \}</math> using the following grammar:


			<math>S \to AS ~\|~ BS ~\|~ C ~\|~ \epsilon</math>

			<math>C \to RC ~\|~ L</math>

			<math>R \xrightarrow[-f]{} RA</math>

			<math>R \xrightarrow[-g]{} RB</math>

			<math>R \xrightarrow[\#]{} \epsilon</math>

			<math>A \xrightarrow[+f]{} a</math>

			<math>B \xrightarrow[+g]{} b</math>

			<math>L \xrightarrow[-f]{} La ~\|~ a</math>

			<math>L \xrightarrow[-g]{} Lb ~\|~ b</math>


			A derivation for the string ''ababab'' is as follows:


			<math>\frac{S}{[\#]} \to \frac{AS}{[\#]} \to \frac{aS}{[\#f]} \to \frac{aBS}{[\#f]} \to \frac{abS}{[\#fg]} \to \frac{abC}{[\#fg]} \to \frac{abRC}{[\#fg]} \to \frac{abRBC}{[\#f]}</math>


			: <math>\frac{abRABC}{[\#]} \to \frac{abABC}{[\#]} \to \frac{abaBC}{[\#f]} \to \frac{ababC}{[\#fg]} \to \frac{ababL}{[\#fg]} \to \frac{ababLb}{[\#f]} \to \frac{ababab}{[\#]}</math>


			A similar derivation follows for ''abbabbabb'', ''aaabaaabaaabaaab'', and other such sentences.

			==Computational Power==

			The global index languages are a subset of the context sensitive languages, and a superset of the context free languages. While it is known that GIGs can generate the MIX/Bach language <math>\{ p(a^n b^n c^n) : n \geq 1 \}</math>, where ''p'' is the string permutation function, and thus are capable of generating non-indexed languages, it is not known whether or not all IGs are also GIGs. It is entirely possible that GIGs and IGs describe merely-overlapping subsets of the CSLs.

			==trGIGs==

			A subclass of GIGs is the class of trGIGs, which make the pop and push rules uniform, by requiring that pop rules also introduce at least one terminal symbol into the derivation.

			===Example===

			An example of such a grammar, characterizing the language <math>\{a^m b^n c^m d^n : m, n \geq 1 \}</math>, is:

			<math>
			\begin{align}
			S & \to AD \\
			A & \to aAc ~\|~ aBc \\
			B & \xrightarrow[+f]{} bB ~\|~ b \\
			D & \xrightarrow[-f]{} dD ~\|~ d \\
			\end{align}
			</math>


			The derivation for the string ''aabbbccddd'' is then:

			<math>
			\begin{align}
			\frac{S}{[\#]} & \to \frac{AD}{[\#]} \to \frac{aAcD}{[\#]} \to \frac{aaBccD}{[\#]} \to \frac{aabBccD}{[\#f]} \to \frac{aabbBccD}{[\#ff]} \\
			& \to \frac{aabbbccD}{[\#fff]} \to \frac{aabbbccdD}{[\#ff]} \to \frac{aabbbccddD}{[\#f]} \to \frac{aabbbccddd}{[\#]} \\
			\end{align}
			</math>

			==References==
			<references/>

			{{Formal languages and grammars}}

			[[Category:Formal languages]]
			[[Category:Grammar frameworks]]

en>Rjwilmsi: Journal cites, added 1 DOI, using AWB (8079)

2012-06-19T09:29:19Z

Journal cites, added 1 DOI, using AWB (8079)

New page

Hello! My name is Alisha. I am happy that I can join to the entire world. I live in France, in the region. I dream to check out the different countries, to obtain acquainted with fascinating individuals.<br><br>my web page; [http://www.olwallpaper.com/profile/vigula Biking for modern life mountain bike sizing.]

Neighborly polytope - Revision history

en>Wavelength: inserting 1 hyphen: —> "higher-dimensional"—User talk:Wavelength#Hyphenation [to Archive 6]

en>YuriYoghi at 07:04, 27 May 2013

en>Rjwilmsi: Journal cites, added 1 DOI, using AWB (8079)