翻訳と辞書 Words near each other ・ Semi-Soet ・ Semi-solid metal casting ・ Semi-speaker ・ Semi-square (astrological aspect) ・ Semi-steel ・ Semi-structured data ・ Semi-structured interview ・ Semi-structured model ・ Semi-submarine ・ Semi-submersible ・ Semi-supervised learning ・ Semi-syllabary ・ Semi-syllable ・ Semi-symmetric graph ・ Semi-synchronous orbit ・ Semi-Thue system ・ Semi-Toned ・ Semi-Tough ・ Semi-trailer ・ Semi-trailer truck ・ Semi-variable cost ・ Semi-vegetarianism ・ Semi-virtual diskette ・ Semi-Yao graph ・ Semi.Official ・ SemiAccurate ・ Semiahmoo ・ Semiahmoo Bay ・ Semiahmoo First Nation ・ Semiahmoo Harbor Light Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Semi-Thue system ： ウィキペディア英語版 Semi-Thue system In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation $R$ between fixed strings over the alphabet, called rewrite rules, denoted by $s\backslash rightarrow\; t$, an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is $usv\backslash rightarrow\; utv$, where $s$, $t$, $u$, and $v$ are strings. 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 for monoids and groups. 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.〔Book and Otto, p. 36〕 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— this result was obtained independently by Emil Post and A. A. Markov Jr.〔Abramsky et al. p. 416〕〔Salomaa et al., p.444〕 ==Definition== A string rewriting system or semi-Thue system is a tuple $(\backslash Sigma,\; R)$ where * is an alphabet, usually assumed finite.〔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.〕 The elements of the set $\backslash Sigma^$ * ( * is the Kleene star here) are finite (possibly empty) strings on , sometimes called ''words'' in formal languages; we will simply call them strings here. * is a binary relation on strings from , i.e., $R\; \backslash subseteq\; \backslash Sigma^$ * \times \Sigma^ *. Each element $(u,v)\; \backslash in\; R$ is called a ''(rewriting) rule'' and is usually written $u\; \backslash rightarrow\; v$. If the relation is symmetric, then the system is called a Thue system. The rewriting rules in can be naturally extended to other strings in $\backslash Sigma^$ * by allowing substrings to be rewritten according to . More formally, the one-step rewriting relation relation $\backslash xrightarrow()$ is a relation on $\backslash Sigma^$ *, the pair $(\backslash Sigma^$ *, \xrightarrow() (e.g. $\backslash xrightarrow()\; \backslash \; s\_2\; \backslash \; \backslash xrightarrow()$ (see abstract rewriting system#Basic notions). This is called the rewriting relation or reduction relation on $\backslash Sigma^$ * induced by . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Semi-Thue system」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.