|
|
| Line 1: |
Line 1: |
| In [[theoretical computer science]] and [[mathematical logic]] a '''string rewriting system''' ('''SRS'''), historically called a '''semi-Thue system''', is a [[rewriting]] system over [[String (computer science)|strings]] from a (usually [[Finite set|finite]]) [[Alphabet (computer science)|alphabet]]. Given a [[binary relation]] <math>R</math> between fixed strings in the alphabet, called '''rewrite rules''', denoted by <math>s\rightarrow t</math>, an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as [[substring]]s, that is <math>usv\rightarrow utv</math>, where <math>s</math>, <math>t</math>, <math>u</math>, and <math>v</math> are strings.
| | The '''Automated Readability Index (ARI)''' is a [[readability test]] designed to gauge the understandability of a text. Like the [[Flesch-Kincaid Readability Test|Flesch-Kincaid]] Grade Level, [[Gunning Fog Index]], [[SMOG Index]], [[Fry Readability Formula]], and [[Coleman-Liau Index]], it produces an approximate representation of the [[Grade levels#USA and Canada|US grade level]] needed to comprehend the text. |
|
| |
|
| The notion of a semi-Thue system essentially coincides with the [[presentation of a monoid]]. Thus they constitute a natural framework for solving the [[word problem (mathematics)|word problem]] for monoids and groups. | | The formula for calculating the Automated Readability Index is given below: |
|
| |
|
| An SRS can be defined directly as an [[abstract rewriting system]]. It can also be seen as a restricted kind of a [[term rewriting]] system. As a formalism, string rewriting systems are [[Turing complete]]. The semi-Thue name comes from the Norwegian mathematician [[Axel Thue]], who introduced systematic treatment of string rewriting systems in a 1914 paper.<ref>Book and Otto, p. 36</ref> Thue introduced this notion hoping to solve the word problem for finitely presented semigroups. It wasn't until 1947 the problem was shown to be [[undecidable problem|undecidable]]— this result was obtained independently by [[Emil Post]] and [[Andrey Markov (Soviet mathematician)|A. A. Markov Jr.]]<ref>Abramsky et al. p. 416</ref><ref>Salomaa et al., p.444</ref>
| | :<math> |
| | 4.71 \left (\frac{\mbox{characters}}{\mbox{words}} \right) + 0.5 \left (\frac{\mbox{words}}{\mbox{sentences}} \right) - 21.43 |
| | </math> |
|
| |
|
| ==Definition==
| | where ''characters'' is the number of letters, numbers, and punctuation marks, ''words'' is the number of spaces, and ''sentences'' is the number of sentences. Sentences were counted by hand as each text was typed. |
|
| |
|
| A '''string rewriting system''' or '''semi-Thue system''' is a [[tuple]] <math>(\Sigma, R)</math> where
| | As a rough guide, US grade level 1 corresponds to ages 6 to 8. Reading level grade 8 corresponds to the typical reading level of a 14 year-old US child. Grade 12, the highest US secondary school grade before college, corresponds to the reading level of a 17 year-old. |
| * <math>\Sigma</math> is an alphabet, usually assumed finite.<ref>In Book and Otto a semi-Thue system is defined over a finite alphabet through most of the book, except chapter 7 when monoid presentation are introduced, when this assumption is quietly dropped.</ref> The elements of the set <math>\Sigma^*</math> (* is the [[Kleene star]] here) are finite (possibly empty) strings on <math>\Sigma</math>, sometimes called ''words'' in [[formal languages]]; we will simply call them strings here.
| |
| * <math>R</math> is a [[binary relation]] on strings from <math>\Sigma</math>, i.e., <math>R \subseteq \Sigma^* \times \Sigma^*.</math> Each element <math>(u,v) \in R</math> is called a ''(rewriting) rule'' and is usually written <math>u \rightarrow v</math>.
| |
|
| |
|
| If the relation <math>R</math> is [[symmetric relation|symmetric]], then the system is called a '''Thue system'''.
| | Unlike the other indices, the ARI, along with the Coleman-Liau, relies on a factor of characters per word, instead of the usual syllables per word. Although opinion varies on its accuracy as compared to the syllables/word and complex words indices, characters/word is often faster to calculate, as the number of characters is more readily and accurately counted by computer programs than syllables. In fact, this index was designed for real-time monitoring of readability on electric typewriters.<ref>{{cite journal |
| | | author = Senter, R.J. |
| | |author2= Smith, E.A. |
| | | date = November 1967 |
| | | title = Automated Readability Index. |
| | | url = http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0667273 |
| | | publisher = [[Wright-Patterson Air Force Base]] |
| | | id = AMRL-TR-6620 |
| | | page = iii |
| | | accessdate = 2012-03-18 |
| | }}</ref> |
|
| |
|
| The rewriting rules in <math>R</math> can be naturally extended to other strings in <math>\Sigma^*</math> by allowing substrings to be rewritten according to <math>R</math>. More formally, the '''one-step rewriting relation''' relation <math>\rightarrow_R</math> induced by <math>R</math> on <math>\Sigma^*</math> for any strings <math>s</math>, and <math>t</math> in <math>\Sigma^*</math>:
| | ==Notes== |
|
| |
|
| : <math>s \rightarrow_R t</math> if and only if there exist <math>x</math>, <math>y</math>, <math>u</math>, <math>v</math> in <math>\Sigma^*</math> such that <math>s = xuy</math>, <math>t = xvy</math>, and <math>u \rightarrow v</math>.
| | <references/> |
|
| |
|
| Since <math>\rightarrow_R</math> is a relation on <math>\Sigma^*</math>, the pair <math>(\Sigma^*, \rightarrow_R)</math> fits the definition of an [[abstract rewriting system]]. Obviously <math>R</math> is a subset of <math>\rightarrow_R</math>. Some authors use a different notation for the arrow in <math>\rightarrow_R</math> (e.g. <math>\Rightarrow_R</math>) in order to distinguish it from <math>R</math> itself (<math>\rightarrow</math>) because they later want to be able to drop the subscript and still avoid confusion between <math>R</math> and the one-step rewrite induced by <math>R</math>.
| | ==External links== |
| | *[http://www.online-utility.org/english/readability_test_and_improve.jsp Online readability tests] - finds ARI and other indices, suggestions how to improve readability |
| | *[http://www.editcentral.com Readability calculators] - six readability statistics |
|
| |
|
| Clearly in a semi-Thue system we can form a (finite or infinite) sequence of strings produced by starting with an initial string <math>s_0 \in \Sigma^*</math> and repeatedly rewriting it by making one substring-replacement at a time:
| | [[Category:Readability tests]] |
|
| |
|
| :<math>s_0 \ \rightarrow_R \ s_1 \ \rightarrow_R \ s_2 \ \rightarrow_R \ \ldots </math>
| | [[da:LIX]] |
| | | [[no:Lesbarhetsindeks]] |
| A zero-or-more-steps rewriting like this is captured by the [[reflexive transitive closure]] of <math>\rightarrow_R</math>, denoted by <math>\stackrel{*}{\rightarrow}_R</math> (see [[abstract rewriting system#Basic notions]]). This is called the '''rewriting relation''' or '''reduction relation''' on <math>\Sigma^*</math> induced by <math>R</math>.
| | [[sv:LIX]] |
| | |
| == Thue congruence ==
| |
| | |
| In general, the set <math>\Sigma^*</math> of strings on an alphabet forms a [[free monoid]] together with the [[binary operation]] of [[string concatenation]] (denoted as <math>\cdot</math> and written multiplicatively by dropping the symbol). In a SRS, the reduction relation <math>\stackrel{*}{\rightarrow}_R</math> is compatible with the monoid operation, meaning that <math>x\stackrel{*}{\rightarrow}_R y</math> implies <math>uxv\stackrel{*}{\rightarrow}_R uyv</math> for all strings <math>x</math>, <math>y</math>, <math>u</math>, <math>v</math> in <math>\Sigma^*</math>. Since <math>\stackrel{*}{\rightarrow}_R</math> is by definition a [[preorder]], <math>(\Sigma^*, \cdot, \stackrel{*}{\rightarrow}_R)</math> forms a [[preordered monoid]].
| |
| | |
| Similarly, the [[reflexive transitive symmetric closure]] of <math>\rightarrow_R</math>, denoted <math>\stackrel{*}{\leftrightarrow}_R</math> (see [[abstract rewriting system#Basic notions]]), is a [[Congruence relation|congruence]], meaning it is an [[equivalence relation]] (by definition) and it is also compatible with string concatenation. The relation <math>\stackrel{*}{\leftrightarrow}_R</math> is called the '''Thue congruence''' generated by <math>R</math>. In a Thue system, i.e. if <math>R</math> is symmetric, the rewrite relation <math>\stackrel{*}{\rightarrow}_R</math> coincides with the Thue congruence <math>\stackrel{*}{\leftrightarrow}_R</math>.
| |
| | |
| == Factor monoid and monoid presentations ==
| |
| Since <math>\stackrel{*}{\leftrightarrow}_R</math> is a congruence, we can define the '''factor monoid''' <math>\mathcal{M}_R = \Sigma^*/\stackrel{*}{\leftrightarrow}_R</math> of the [[free monoid]] <math>\Sigma^*</math> by the Thue congruence in the [[factor monoid|usual manner]]. If a monoid <math>\mathcal{M}</math> is [[isomorphic]] with <math>\mathcal{M}_R</math>, then the semi-Thue system <math>(\Sigma, R)</math> is called a [[monoid presentation]] of <math>\mathcal{M}</math>.
| |
| | |
| We immediately get some very useful connections with other areas of algebra. For example, the alphabet {''a'', ''b''} with the rules { ''ab'' → ε, ''ba'' → ε }, where ε is the [[empty string]], is a presentation of the [[free group]] on one generator. If instead the rules are just { ''ab'' → ε }, then we obtain a presentation of the [[bicyclic monoid]].
| |
| | |
| The importance of semi-Thue systems as presentation of monoids is made stronger by the following:
| |
| | |
| '''Theorem''': Every monoid has a presentation of the form <math>(\Sigma, R)</math>, thus it may be always be presented by a semi-Thue system, possibly over an infinite alphabet.<ref>Book and Otto, Theorem 7.1.7, p. 149</ref>
| |
| | |
| In this context, the set <math>\Sigma</math> is called the '''set of generators''' of <math>\mathcal{M}</math>, and <math>R</math> is called the set of '''defining relations''' <math>\mathcal{M}</math>. We can immediately classify monoids based on their presentation. <math>\mathcal{M}</math> is called
| |
| * '''finitely generated''' if <math>\Sigma</math> is finite.
| |
| * '''finitely presented''' if both <math>\Sigma</math> and <math>R</math> are finite.
| |
| | |
| == The word problem for semi-Thue systems ==
| |
| | |
| The word problem for semi-Thue systems can be stated as follows: Given a semi-Thue system <math>T:=(\Sigma, R)</math> and two words (strings) <math>u, v \in \Sigma^*</math>, can <math>u</math> be transformed into <math>v</math> by applying rules from <math>R</math>? This problem is [[Undecidable problem|undecidable]], i.e. there is no general algorithm for solving this problem. This even holds if we limit the input to finite systems.
| |
| | |
| Martin Davis offers the lay reader a two-page proof in his article "What is a Computation?" pp. 258–259 with commentary p. 257. Davis casts the proof in this manner: "Invent [a word problem] whose solution would lead to a solution to the [[halting problem]]."
| |
| | |
| == Connections with other notions ==
| |
| | |
| A semi-Thue system is also a [[term-rewriting]] system—one that has [[monadic (arity)|monadic]] words (functions) ending in the same variable as left- and right-hand side terms,<ref>Nachum Dershowitz and Jean-Pierre Jouannaud. [http://citeseer.ist.psu.edu/dershowitz90rewrite.html Rewrite Systems] (1990) p. 6</ref> e.g. a term rule <math>f_2(f_1(x)) \rightarrow g(x)</math> is equivalent with the string rule <math>f_1f_2 \rightarrow g</math>.
| |
| | |
| A semi-Thue system is also a special type of [[Post canonical system]], but every Post canonical system can also be reduced to an SRS. Both formalism are [[Turing complete]], and thus equivalent to [[Noam Chomsky]]'s [[unrestricted grammar]]s, which are sometimes called ''semi-Thue grammars''.<ref>D.I.A. Cohen, Introduction to Computer Theory, 2nd ed., Wiley-India, 2007, ISBN 81-265-1334-9, p.572</ref> A [[formal grammar]] only differs from a semi-Thue system by the separation of the alphabet in terminals and non-terminals, and the fixation of a starting symbol amongst non-terminals. A minority of authors actually define a semi-Thue system as a triple <math>(\Sigma, A, R)</math>, where <math>A\subseteq\Sigma^*</math> is called the ''set of axioms''. Under this "generative" definition of semi-Thue system, an unrestricted grammar is just a semi-Thue system with a single axiom in which one partitions the alphabet in terminals and non-terminals, and makes the axiom a nonterminal.<ref>Dan A. Simovici, Richard L. Tenney, ''Theory of formal languages with applications'', World Scientific, 1999 ISBN 981-02-3729-4, chapter 4</ref> The simple artifice of partitioning the alphabet in terminals and non-terminals is a powerful one; it allows the definition of the [[Chomsky hierarchy]] based on the what combination of terminals and non-terminals rules contain. This was a crucial development in the theory of [[formal languages]].
| |
| | |
| ==History and importance==
| |
| Semi-Thue systems were developed as part of a program to add additional constructs to [[logic]], so as to create systems such as [[propositional logic]], that would allow general mathematical theorems to be expressed in a [[formal language]], and then proven and verified in an automatic, mechanical fashion. The hope was that the act of [[theorem proving]] could then be reduced to a set of defined manipulations on a set of strings. It was subsequently realized that semi-Thue systems are isomorphic to [[unrestricted grammar]]s, which in turn are known to be isomorphic to [[Turing machine]]s. This method of research succeeded and now computers can be used to verify the proofs of mathematic and logical theorems.
| |
| | |
| At the suggestion of [[Alonzo Church]], [[Emil Post]] in a paper published in 1947, first proved "a certain Problem of Thue" to be unsolvable, what [[Martin Davis]] states as "...the first unsolvability proof for a problem from classical mathematics -- in this case the word problem for semigroups." (Undecidable p. 292)
| |
| | |
| Davis [ibid] asserts that the proof was offered independently by A. A. Markov (C. R. (Doklady) Acad. Sci. U.S.S.R. (n.s.) 55(1947), pp. 583–586.
| |
| | |
| == See also ==
| |
| | |
| * [[L-system]]
| |
| * [[MU puzzle]]
| |
| | |
| == Notes ==
| |
| {{reflist}}
| |
| | |
| == References ==
| |
| | |
| === Monographs ===
| |
| | |
| * [[Ronald V. Book]] and Friedrich Otto, ''String-rewriting Systems'', Springer, 1993, ISBN 0-387-97965-4.
| |
| * Matthias Jantzen, ''Confluent string rewriting'', Birkhäuser, 1988, ISBN 0-387-13715-7.
| |
| | |
| === Textbooks ===
| |
| | |
| * [[Martin Davis]], Ron Sigal, Elaine J. Weyuker, ''Computability, complexity, and languages: fundamentals of theoretical computer science'', 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1, chapter 7
| |
| * Elaine Rich, ''Automata, computability and complexity: theory and applications'', Prentice Hall, 2007, ISBN 0-13-228806-0, chapter 23.5.
| |
| | |
| === Surveys ===
| |
| | |
| <!--TODO: find article names/authors from the reflist above.-->
| |
| * Samson Abramsky, Dov M. Gabbay, Thomas S. E. Maibaum (ed.), ''Handbook of Logic in Computer Science: Semantic modelling'', Oxford University Press, 1995, ISBN 0-19-853780-8.
| |
| * Grzegorz Rozenberg, Arto Salomaa (ed.), ''Handbook of Formal Languages: Word, language, grammar'', Springer, 1997, ISBN 3-540-60420-0.
| |
| | |
| === Landmark papers ===
| |
| | |
| * [[Emil Post]] (1947), ''Recursive Unsolvability of a Problem of Thue'', The Journal of Symbolic Logic, vol. 12 (1947) pp. 1–11. Reprinted in [[Martin Davis]] ed. (1965), ''The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions'', Raven Press, New York. pp. 293ff
| |
| | |
| [[Category:Formal languages]]
| |
| [[Category:Theory of computation]] | |
| [[Category:Rewriting systems]]
| |
| | |
| [[ja:文字列書き換え系]]
| |
The Automated Readability Index (ARI) is a readability test designed to gauge the understandability of a text. Like the Flesch-Kincaid Grade Level, Gunning Fog Index, SMOG Index, Fry Readability Formula, and Coleman-Liau Index, it produces an approximate representation of the US grade level needed to comprehend the text.
The formula for calculating the Automated Readability Index is given below:
where characters is the number of letters, numbers, and punctuation marks, words is the number of spaces, and sentences is the number of sentences. Sentences were counted by hand as each text was typed.
As a rough guide, US grade level 1 corresponds to ages 6 to 8. Reading level grade 8 corresponds to the typical reading level of a 14 year-old US child. Grade 12, the highest US secondary school grade before college, corresponds to the reading level of a 17 year-old.
Unlike the other indices, the ARI, along with the Coleman-Liau, relies on a factor of characters per word, instead of the usual syllables per word. Although opinion varies on its accuracy as compared to the syllables/word and complex words indices, characters/word is often faster to calculate, as the number of characters is more readily and accurately counted by computer programs than syllables. In fact, this index was designed for real-time monitoring of readability on electric typewriters.[1]
Notes
- ↑ One of the biggest reasons investing in a Singapore new launch is an effective things is as a result of it is doable to be lent massive quantities of money at very low interest rates that you should utilize to purchase it. Then, if property values continue to go up, then you'll get a really high return on funding (ROI). Simply make sure you purchase one of the higher properties, reminiscent of the ones at Fernvale the Riverbank or any Singapore landed property Get Earnings by means of Renting
In its statement, the singapore property listing - website link, government claimed that the majority citizens buying their first residence won't be hurt by the new measures. Some concessions can even be prolonged to chose teams of consumers, similar to married couples with a minimum of one Singaporean partner who are purchasing their second property so long as they intend to promote their first residential property. Lower the LTV limit on housing loans granted by monetary establishments regulated by MAS from 70% to 60% for property purchasers who are individuals with a number of outstanding housing loans on the time of the brand new housing purchase. Singapore Property Measures - 30 August 2010 The most popular seek for the number of bedrooms in Singapore is 4, followed by 2 and three. Lush Acres EC @ Sengkang
Discover out more about real estate funding in the area, together with info on international funding incentives and property possession. Many Singaporeans have been investing in property across the causeway in recent years, attracted by comparatively low prices. However, those who need to exit their investments quickly are likely to face significant challenges when trying to sell their property – and could finally be stuck with a property they can't sell. Career improvement programmes, in-house valuation, auctions and administrative help, venture advertising and marketing, skilled talks and traisning are continuously planned for the sales associates to help them obtain better outcomes for his or her shoppers while at Knight Frank Singapore. No change Present Rules
Extending the tax exemption would help. The exemption, which may be as a lot as $2 million per family, covers individuals who negotiate a principal reduction on their existing mortgage, sell their house short (i.e., for lower than the excellent loans), or take part in a foreclosure course of. An extension of theexemption would seem like a common-sense means to assist stabilize the housing market, but the political turmoil around the fiscal-cliff negotiations means widespread sense could not win out. Home Minority Chief Nancy Pelosi (D-Calif.) believes that the mortgage relief provision will be on the table during the grand-cut price talks, in response to communications director Nadeam Elshami. Buying or promoting of blue mild bulbs is unlawful.
A vendor's stamp duty has been launched on industrial property for the primary time, at rates ranging from 5 per cent to 15 per cent. The Authorities might be trying to reassure the market that they aren't in opposition to foreigners and PRs investing in Singapore's property market. They imposed these measures because of extenuating components available in the market." The sale of new dual-key EC models will even be restricted to multi-generational households only. The models have two separate entrances, permitting grandparents, for example, to dwell separately. The vendor's stamp obligation takes effect right this moment and applies to industrial property and plots which might be offered inside three years of the date of buy. JLL named Best Performing Property Brand for second year running
The data offered is for normal info purposes only and isn't supposed to be personalised investment or monetary advice. Motley Fool Singapore contributor Stanley Lim would not personal shares in any corporations talked about. Singapore private home costs increased by 1.eight% within the fourth quarter of 2012, up from 0.6% within the earlier quarter. Resale prices of government-built HDB residences which are usually bought by Singaporeans, elevated by 2.5%, quarter on quarter, the quickest acquire in five quarters. And industrial property, prices are actually double the levels of three years ago. No withholding tax in the event you sell your property. All your local information regarding vital HDB policies, condominium launches, land growth, commercial property and more
There are various methods to go about discovering the precise property. Some local newspapers (together with the Straits Instances ) have categorised property sections and many local property brokers have websites. Now there are some specifics to consider when buying a 'new launch' rental. Intended use of the unit Every sale begins with 10 p.c low cost for finish of season sale; changes to 20 % discount storewide; follows by additional reduction of fiftyand ends with last discount of 70 % or extra. Typically there is even a warehouse sale or transferring out sale with huge mark-down of costs for stock clearance. Deborah Regulation from Expat Realtor shares her property market update, plus prime rental residences and houses at the moment available to lease Esparina EC @ Sengkang
External links
da:LIX
no:Lesbarhetsindeks
sv:LIX