東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Complexity Theoretic Parallels Among...

Xie, Jingnan.

Linked to FindBook

Google Book

Amazon

博客來

Complexity Theoretic Parallels Among Automata, Formal Languages and Real Variables Including Multi-Patterns, L-Systems and Cellular Automata.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Complexity Theoretic Parallels Among Automata, Formal Languages and Real Variables Including Multi-Patterns, L-Systems and Cellular Automata./
Author:	Xie, Jingnan.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2017,
Description:	112 p.
Notes:	Source: Dissertation Abstracts International, Volume: 78-09(E), Section: B.
Contained By:	Dissertation Abstracts International78-09B(E).
Subject:	Computer science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10272502
ISBN:	9781369721829

Complexity Theoretic Parallels Among Automata, Formal Languages and Real Variables Including Multi-Patterns, L-Systems and Cellular Automata.
Xie, Jingnan.

Complexity Theoretic Parallels Among Automata, Formal Languages and Real Variables Including Multi-Patterns, L-Systems and Cellular Automata. - Ann Arbor : ProQuest Dissertations & Theses, 2017 - 112 p.

Source: Dissertation Abstracts International, Volume: 78-09(E), Section: B.

Thesis (Ph.D.)--State University of New York at Albany, 2017.

In this dissertation, we emphasize productiveness not just undecidability since productiveness implies constructive incompleteness. Analogues of Rice's Theorem for different classes of languages are investigated, refined and generalized. In particular, several sufficient but general conditions are presented for predicates to be as hard as some widely discussed predicates such as "= O" and "= {0,1}*". These conditions provide several general methods for proving complexity/productiveness results and apply to a large number of simple and natural predicates. As the first step in applying these general methods, we investigate the complexity/productiveness of the predicates "= O", "= {0,1}*" and other predicates that can be useful sources of many-one reductions for different classes of languages. Then we use very efficient many-one reductions of these basic source predicates to prove many new non-polynomial complexity lower bounds and productiveness results. Moreover, we study the complexity/productiveness of predicates for easily recognizable subsets of instances with important semantic properties. Because of the efficiency of our reductions, intuitively these reductions can preserve many levels of complexity.

ISBN: 9781369721829Subjects--Topical Terms:

523869
Computer science.

Complexity Theoretic Parallels Among Automata, Formal Languages and Real Variables Including Multi-Patterns, L-Systems and Cellular Automata.
LDR:03985nmm a2200313 4500 001 2126629
005 20171128150728.5
008 180830s2017 ||||||||||||||||| ||eng d
020 $a 9781369721829
035 $a (MiAaPQ)AAI10272502
035 $a AAI10272502
040 $a MiAaPQ $c MiAaPQ
100 1 $a Xie, Jingnan. $3 3288738
245 1 0 $a Complexity Theoretic Parallels Among Automata, Formal Languages and Real Variables Including Multi-Patterns, L-Systems and Cellular Automata.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2017
300 $a 112 p.
500 $a Source: Dissertation Abstracts International, Volume: 78-09(E), Section: B.
500 $a Adviser: Harry B. Hunt, III.
502 $a Thesis (Ph.D.)--State University of New York at Albany, 2017.
520 $a In this dissertation, we emphasize productiveness not just undecidability since productiveness implies constructive incompleteness. Analogues of Rice's Theorem for different classes of languages are investigated, refined and generalized. In particular, several sufficient but general conditions are presented for predicates to be as hard as some widely discussed predicates such as "= O" and "= {0,1}*". These conditions provide several general methods for proving complexity/productiveness results and apply to a large number of simple and natural predicates. As the first step in applying these general methods, we investigate the complexity/productiveness of the predicates "= O", "= {0,1}*" and other predicates that can be useful sources of many-one reductions for different classes of languages. Then we use very efficient many-one reductions of these basic source predicates to prove many new non-polynomial complexity lower bounds and productiveness results. Moreover, we study the complexity/productiveness of predicates for easily recognizable subsets of instances with important semantic properties. Because of the efficiency of our reductions, intuitively these reductions can preserve many levels of complexity.
520 $a We apply our general methods to pattern languages and multi-pattern languages. Interrelations between multi-pattern languages (or pattern languages) and standard classes of languages such as context-free languages and regular languages are studied. A way to study the descriptional complexity of standard language descriptors (for examples, context-free grammars and regular expressions) and multi-patterns is illustrated. We apply our general methods to several generalizations of regular expressions. A productiveness result for the predicate "= {0,1}*" is established for synchronized regular expressions. Because of this, many new productiveness results for synchronized regular expressions follow easily. We also apply our general methods to several classes of Lindenmayer systems and of cellular automata. A way of studying the complexity/productiveness of the 0Lness problem is developed and many new results follow from it. For real time one-way cellular automata, we observe that the predicates "= O" and "= {0,1}*" are both productive. Because vi of this, many more general results are presented. For two-way cellular automata, we prove a strong meta-theorem and give a complete characterization for testing containment of any fixed two-way cellular automaton language.
520 $a Finally, we generalize our methods and apply them to the theory of functions of real variables. In rings, the equivalence to identically 0 function problem which is an analogue of "= O" is studied. We show that the equivalence to identically 0 function problem for some classes of elementary functions is productive for different domains including open and closed bounded intervals of real numbers. Two initial results for real fields are also presented.
590 $a School code: 0668.
650 4 $a Computer science. $3 523869
650 4 $a Theoretical mathematics. $3 3173530
690 $a 0984
690 $a 0642
710 2 $a State University of New York at Albany. $b Computer Science. $3 1681272
773 0 $t Dissertation Abstracts International $g 78-09B(E).
790 $a 0668
791 $a Ph.D.
792 $a 2017
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10272502