Longest repeated substring problem - Revision history

en>Anurag.x.singh: Added External link for C implementation of Longest Repeated Substring using Suffix Tree

2014-11-14T18:07:26Z

Added External link for C implementation of Longest Repeated Substring using Suffix Tree

← Older revision		Revision as of 20:07, 14 November 2014
Line 1:		Line 1:
	~~An '''[[Ordinal number\|ω]]-language'''~~ is ~~a [[Set (mathematics)\|set]] of infinite-length sequences of [[symbol (formal)\|symbols]].~~		Hi there, I am Alyson Boon even though it is not the title on my birth certificate. To climb is something I truly appreciate doing. North Carolina is the place he loves most but now he is considering other options. Invoicing is what I do for a residing but I've usually needed my personal business.<br><br>Also visit my web site - [http://brazil.amor-amore.com/irboothe psychic readings]

	~~==Formal definition==~~

	~~Let Σ be a set of symbols (~~not ~~necessarily finite). Following~~ the ~~standard definition from [[formal language]] theory, Σ<sup>*</sup> is the set of all ''finite'' words over Σ~~. ~~Every finite word has a length, which~~ is, obviously, a natural number. Given a word ''w'' of length ''n'', ''w'' can be viewed as a function from the set {0,1,...,''n''-1} → Σ. The infinite words, or ω-words, can likewise be viewed as functions from <math>\mathbb{N}</math> to Σ, with the value at ''i'' giving the symbol at position ''i''. The set of all infinite words over Σ is denoted Σ<sup>ω</sup>. The set of all finite ''and'' infinite words over Σ is sometimes written Σ<sup>∞</sup>.

	~~Thus, an ω-language ''L'' over Σ is a [[subset]] of Σ<sup>ω</sup>.~~

	~~==Operations==~~

	~~Some common operations defined on ω-languages are:~~

	* ''Intersection and union''. Given ω-languages ''L'' and ''M'', both ''L'' ∪ ''M'' and ''L'' ∩ ''M'' are ω-languages.
	* ''Left catenation''. Let ''L'' be an ω-language, and ''K'' be a language of finite words only. Then ''K'' can be catenated on the left ''only'' to ''L'' to yield the new ω-language ''KL''.
	* ''Omega (infinite iteration)''. ~~As the notation hints, the operation (<math>\cdot</math>)<sup>ω</sup>~~ is the ~~infinite version of the [[Kleene star]] operator on finite-length languages. Given a formal language ''L'', ''L''<sup>ω</sup>~~ is ~~the ω-language of all infinite sequence of words from ''L''; in the functional view, of all functions <math>\mathbb{N}</math>→''L''.~~
	* ''Prefixes''. ~~Let ''w'' be an ω-word. Then the formal language Pref(''w'') contains every ''finite'' [[Prefix (computer science)\|prefix]] of ''w''.~~
	* ''Limit''. Given a finite-length language ''L'', an ω-word ''w'' is in the ''limit'' of ''L'' if and only if Pref(''w'') ∩ ''L'' is ~~an ''infinite'' set. In other words,~~ for ~~an arbitrarily large natural number ''n'', it is always possible to choose some word in ''L'', whose length is greater than ''n'', ''and'' which is~~ a ~~prefix of ''w'~~'. ~~The limit operation on ''L'' can be written ''L''<sup>δ~~<~~/sup~~> or <~~math>\vec{L}</math~~>.

	~~==Distance between ω~~-~~words==~~

	~~The set Σ<sup>ω</sup> can be made into a~~ [~~[metric space]] by definition of the [[metric (mathematics)\|metric]] d~~:~~Σ<sup>ω<~~/~~sup> × Σ<sup>ω<~~/~~sup> → '''R''' as:~~

	~~: '''if''' ''w'' and ''v'' share any finite prefix, then d(''w'',''v'')= inf {2<sup>-\|''x''\|</sup> : ''x'' in Σ<sup>*</sup>, and ''x'' in both Pref(''w'') and Pref(''v'') }.~~
	~~: '''otherwise''' d(''w'', ''v'')=1~~

	where \|''x''\| is interpreted as "the length of ''x''" (number of symbols in ''x''), and '''inf''' is the [[infimum]] over sets of [[real number]]s. If ''w''=''v'', they have no longest finite prefix, and d(''w'',''v'')=0; it can be shown that d satisfies all the other necessary properties of a [[metric (mathematics)\|metric]].

	~~==Important subclasses==~~

	~~The most widely used subclass of the ω~~-languages is the set of [[omega-regular language\|ω-regular languages]], which enjoy the useful property of being recognizable by [[Büchi automaton\|Büchi automata]]; thus the [[decision problem]] of ω-regular language membership is decidable and fairly straightforward to compute.

	~~==Bibliography==~~
	* Perrin, D. and Pin, J-E. "[http://www.liafa.jussieu.fr/~~~jep/Resumes/InfiniteWords.html Infinite Words Automata, Semigroups, Logic and Games]". Pure and Applied Mathematics Vol 141, Elsevier, 2004.~~
	* Staiger, L. "[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=CB21AA7D00A17BADAE650D2B342D7752?doi=10.1.1.48.4015&rep=rep1&type=pdf ω-Languages]". In G. Rozenberg and [[Arto Salomaa\|A. Salomaa]], editors, ''Handbook of Formal Languages'', Volume 3, pages 339-387. Springer-Verlag, Berlin, 1997.
	* Thomas, W. "Automata on Infinite Objects". In [[Jan van Leeuwen]], editor, ''Handbook of Theoretical Computer Science'', Volume B: Formal Models and Semantics, pages 133-192. Elsevier Science Publishers, Amsterdam, 1990.

	~~[[Category:Theory of computation]]~~
	~~[[Category:Formal languages]~~]

en>Tentinator: Reverted 1 good faith edit by 14.139.125.67 using STiki

2013-10-26T14:28:36Z

Reverted 1 good faith edit by 14.139.125.67 using STiki

← Older revision		Revision as of 16:28, 26 October 2013
Line 1:		Line 1:
	~~Greetings~~. Let ~~me begin by telling you~~ the ~~author~~'~~s title~~ - ~~Phebe~~. ~~To perform baseball~~ is the ~~hobby he will by no means quit performing~~. ~~Years~~ in the ~~past we moved~~ to ~~North Dakota. My working day occupation~~ is a ~~meter reader~~.<br><br>~~My website~~ - ~~std testing at home~~ ([http://www.~~ddhelicam~~.~~com~~/~~board_Kurr59~~/~~59568 check here~~])		An '''[[Ordinal number\|ω]]-language''' is a [[Set (mathematics)\|set]] of infinite-length sequences of [[symbol (formal)\|symbols]].

			==Formal definition==

			Let Σ be a set of symbols (not necessarily finite). Following the standard definition from [[formal language]] theory, Σ<sup>*</sup> is the set of all ''finite'' words over Σ. Every finite word has a length, which is, obviously, a natural number. Given a word ''w'' of length ''n'', ''w'' can be viewed as a function from the set {0,1,...,''n''-1} → Σ. The infinite words, or ω-words, can likewise be viewed as functions from <math>\mathbb{N}</math> to Σ, with the value at ''i'' giving the symbol at position ''i''. The set of all infinite words over Σ is denoted Σ<sup>ω</sup>. The set of all finite ''and'' infinite words over Σ is sometimes written Σ<sup>∞</sup>.

			Thus, an ω-language ''L'' over Σ is a [[subset]] of Σ<sup>ω</sup>.

			==Operations==

			Some common operations defined on ω-languages are:

			* ''Intersection and union''. Given ω-languages ''L'' and ''M'', both ''L'' ∪ ''M'' and ''L'' ∩ ''M'' are ω-languages.
			* ''Left catenation''. Let ''L'' be an ω-language, and ''K'' be a language of finite words only. Then ''K'' can be catenated on the left ''only'' to ''L'' to yield the new ω-language ''KL''.
			* ''Omega (infinite iteration)''. As the notation hints, the operation (<math>\cdot</math>)<sup>ω</sup> is the infinite version of the [[Kleene star]] operator on finite-length languages. Given a formal language ''L'', ''L''<sup>ω</sup> is the ω-language of all infinite sequence of words from ''L''; in the functional view, of all functions <math>\mathbb{N}</math>→''L''.
			* ''Prefixes''. Let ''w'' be an ω-word. Then the formal language Pref(''w'') contains every ''finite'' [[Prefix (computer science)\|prefix]] of ''w''.
			* ''Limit''. Given a finite-length language ''L'', an ω-word ''w'' is in the ''limit'' of ''L'' if and only if Pref(''w'') ∩ ''L'' is an ''infinite'' set. In other words, for an arbitrarily large natural number ''n'', it is always possible to choose some word in ''L'', whose length is greater than ''n'', ''and'' which is a prefix of ''w''. The limit operation on ''L'' can be written ''L''<sup>δ</sup> or <math>\vec{L}</math>.

			==Distance between ω-words==

			The set Σ<sup>ω</sup> can be made into a [[metric space]] by definition of the [[metric (mathematics)\|metric]] d:Σ<sup>ω</sup> × Σ<sup>ω</sup> → '''R''' as:

			: '''if''' ''w'' and ''v'' share any finite prefix, then d(''w'',''v'')= inf {2<sup>-\|''x''\|</sup> : ''x'' in Σ<sup>*</sup>, and ''x'' in both Pref(''w'') and Pref(''v'') }.
			: '''otherwise''' d(''w'', ''v'')=1

			where \|''x''\| is interpreted as "the length of ''x''" (number of symbols in ''x''), and '''inf''' is the [[infimum]] over sets of [[real number]]s. If ''w''=''v'', they have no longest finite prefix, and d(''w'',''v'')=0; it can be shown that d satisfies all the other necessary properties of a [[metric (mathematics)\|metric]].

			==Important subclasses==

			The most widely used subclass of the ω-languages is the set of [[omega-regular language\|ω-regular languages]], which enjoy the useful property of being recognizable by [[Büchi automaton\|Büchi automata]]; thus the [[decision problem]] of ω-regular language membership is decidable and fairly straightforward to compute.

			==Bibliography==
			* Perrin, D. and Pin, J-E. "[http://www.liafa.jussieu.fr/~jep/Resumes/InfiniteWords.html Infinite Words Automata, Semigroups, Logic and Games]". Pure and Applied Mathematics Vol 141, Elsevier, 2004.
			* Staiger, L. "[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=CB21AA7D00A17BADAE650D2B342D7752?doi=10.1.1.48.4015&rep=rep1&type=pdf ω-Languages]". In G. Rozenberg and [[Arto Salomaa\|A. Salomaa]], editors, ''Handbook of Formal Languages'', Volume 3, pages 339-387. Springer-Verlag, Berlin, 1997.
			* Thomas, W. "Automata on Infinite Objects". In [[Jan van Leeuwen]], editor, ''Handbook of Theoretical Computer Science'', Volume B: Formal Models and Semantics, pages 133-192. Elsevier Science Publishers, Amsterdam, 1990.

			[[Category:Theory of computation]]
			[[Category:Formal languages]]

en>Ruud Koot: removed Category:Algorithms on strings; added Category:Problems on strings using HotCat

2011-12-05T03:32:05Z

removed Category:Algorithms on strings; added Category:Problems on strings using HotCat

New page

Greetings. Let me begin by telling you the author's title - Phebe. To perform baseball is the hobby he will by no means quit performing. Years in the past we moved to North Dakota. My working day occupation is a meter reader.<br><br>My website - std testing at home ([http://www.ddhelicam.com/board_Kurr59/59568 check here])