Thesis--University of Florida. / Description based on print version record. Typescript. Vita. Includes bibliographical references (leaves 109-111).

Thesis (M.S. in Computer Science)--Naval Postgraduate School, December 1990. / Thesis Advisor(s): Shimeall, Timothy J. Second Reader: Hefner, Kim A. S. "December 1990." Description based on title screen as viewed on March 31, 2010. DTIC Identifier(s): Computer Program Reliability, System Safety. Author(s) subject terms: Software Safety, Petri Net, Fault Tree, Software Engineering, Integrated System Analysis. Includes bibliographical references (p. 47-51). Also available in print.

Thesis (Ph. D.)--Washington State University, May 2009. / Title from PDF title page (viewed on June 3, 2009). "School of Electrical Engineering and Computer Science." Includes bibliographical references (p. 101-108).

Thesis (M.C.S.)--Carleton University, 1992. / Also available in electronic format on the Internet.

Thesis (Ph.D.) - University of Queensland, 2005. / Includes bibliography.

No description available.

Bibliography: leaves 150-161. This thesis addresses two areas in the field of conceptual structures. The first is the unification of conceptual graphs, and the consequent work in projection and in type hierarchies... The second area of investigation is the definition of constraints, especially real-value constraints on the concept referents, with particular attention to handling constraints during the unification of conceptual graphs.

Equational reasoning with string diagrams provides an intuitive method for proving equations between morphisms in various forms of monoidal category. !-Graphs were introduced with the intention of reasoning with infinite families of string diagrams by allowing repetition of sub-diagrams. However, their combinatoric nature only allows commutative nodes. The aim of this thesis is to extend the !-graph formalism to remove the restriction of commutativity and replace the notion of equational reasoning with a natural deduction system based on first order logic. The first major contribution is the syntactic !-tensor formalism, which enriches Penrose's abstract tensor notation to allow repeated structure via !-boxes. This will allow us to work with many noncommutative theories such as bialgebras, Frobenius algebras, and Hopf algebras, which have applications in quantum information theory. A more subtle consequence of switching to !-tensors is the ability to definitionally extend a theory. We will demonstrate how noncommutativity allows us to define nodes which encapsulate entire diagrams, without inherently assuming the diagram is commutative. This is particularly useful for recursively defining arbitrary arity nodes from fixed arity nodes. For example, we can construct a !-tensor node representing the family of left associated trees of multiplications in a monoid. The ability to recursively define nodes goes hand in hand with proof by induction. This leads to the second major contribution of this thesis, which is !-Logic (!L). We extend previous attempts at equational reasoning to a fully fledged natural deduction system based on positive intuitionistic first order logic, with conjunction, implication, and universal quantification over !-boxes. The key component of !L is the principle of !-box induction. We demonstrate its application by proving how we can transition from fixed to arbitrary arity theories for monoids, antihomomorphisms, bialgebras, and various forms of Frobenius algebras. We also define a semantics for !L, which we use to prove its soundness. Finally, we reintroduce commutativity as an optional property of a morphism, along with another property called symmetry, which describes morphisms which are not affected by cyclic permutations of their edges. Implementing these notions in the !-tensor language allows us to more easily describe theories involving symmetric or commutative morphisms, which we then demonstrate for recursively defined Frobenius algebra nodes.

Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. However, these keyword search semantics and algorithms encounter efficiency or scalability issues. In this thesis, we propose new three generic frameworks or index techniques to address these issues. The thesis results show that the keyword search on massive graphs under different scenarios can be effective and efficient, which would facilitate keyword search services on graphs in the real world. First, we study the keyword search on massive knowledge graphs. In particular, we propose a generic ontology- based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. The novelties of BiG-index reside in using an ontology graph GOnt to summarize and index a data graph G iteratively, to form a hierarchical index structure G. Regarding query evaluation, we transform a keyword search q into Q according to GOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index's applicability, we show popular indexing techniques for keyword search can be easily implemented on top of BiG-index. Our extensive experiments show that BiG-index clearly reduced the runtimes of popular keyword search algorithms. Second, we study the problem of keyword search on public-private graph. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public-private networks has not yet been studied. Hence, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. We select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that span through them. Third, we study the keyword search in distributed graph evaluation systems. In the recent research on query evaluation, parallel evaluation has attracted much interest. However, the study on keyword search on distributed graphs has still been limited. We propose a novel distributed keyword search framework called DKWS. We propose a notify-push paradigm which can exchange the upper bounds of answers across all the workers asynchronously. In particular, the workers notify the coordinator when the local upper bound is refined. The coordinator pushes the refined global upper bound to all the workers. Moreover, we propose an efficient and generic keyword search algorithm for the workers. We have implemented DKWS on top of GRAPE, a distributed graph process system from our previous research collaboration. Extensive experimental results show that DKWS outperforms current-state-of-art techniques

Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. However, these keyword search semantics and algorithms encounter efficiency or scalability issues. In this thesis, we propose new three generic frameworks or index techniques to address these issues. The thesis results show that the keyword search on massive graphs under different scenarios can be effective and efficient, which would facilitate keyword search services on graphs in the real world. First, we study the keyword search on massive knowledge graphs. In particular, we propose a generic ontology- based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. The novelties of BiG-index reside in using an ontology graph GOnt to summarize and index a data graph G iteratively, to form a hierarchical index structure G. Regarding query evaluation, we transform a keyword search q into Q according to GOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index's applicability, we show popular indexing techniques for keyword search can be easily implemented on top of BiG-index. Our extensive experiments show that BiG-index clearly reduced the runtimes of popular keyword search algorithms. Second, we study the problem of keyword search on public-private graph. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public-private networks has not yet been studied. Hence, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. We select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that span through them. Third, we study the keyword search in distributed graph evaluation systems. In the recent research on query evaluation, parallel evaluation has attracted much interest. However, the study on keyword search on distributed graphs has still been limited. We propose a novel distributed keyword search framework called DKWS. We propose a notify-push paradigm which can exchange the upper bounds of answers across all the workers asynchronously. In particular, the workers notify the coordinator when the local upper bound is refined. The coordinator pushes the refined global upper bound to all the workers. Moreover, we propose an efficient and generic keyword search algorithm for the workers. We have implemented DKWS on top of GRAPE, a distributed graph process system from our previous research collaboration. Extensive experimental results show that DKWS outperforms current-state-of-art techniques