Persistent Link:
http://hdl.handle.net/10150/105736
Title:
Matrix Graph Grammars
Author:
Perez Velasco, Pedro Pablo
Citation:
Matrix Graph Grammars 2008-01,
Issue Date:
Jan-2008
URI:
http://hdl.handle.net/10150/105736
Submitted date:
2008-01-07
Abstract:
If the aim of this dissertation had to be summarized in a single sentence, it could be algebraization of graph grammars. An equivalent one would be study of graph dynamics. From the point of view of a computer scientist, graph grammars are a natural generalization of Chomsky grammars for which a purely algebraic approach does not exist up to now. A Chomsky (or string) grammar is, roughly speaking, a precise description of a formal language (which in essence is a set of strings). On a more discrete mathematical style, it can be said that graph grammars â Matrix Graph Grammars in particular â study dynamics of graphs. Ideally, this algebraization would enforce our understanding of grammars in general, providing new analysis techniques and generalizations of concepts, problems and results known so far. In this dissertation we fully develop such theory over the field GF(2) which covers all graph cases, from simple graphs (more attractive for a mathematician) to multidigraphs (more interesting for an applied computer scientist). The theory is presented and its basic properties demonstrated in a first stage, moving to increasingly difficult problems and establishing relations among them.
Type:
Thesis
Language:
en
Keywords:
Computer Science
Local subject classification:
graph dynamics; graph grammars

Full metadata record

DC FieldValue Language
dc.contributor.authorPerez Velasco, Pedro Pabloen_US
dc.date.accessioned2008-01-07T00:00:01Z-
dc.date.available2010-06-18T23:33:24Z-
dc.date.issued2008-01en_US
dc.date.submitted2008-01-07en_US
dc.identifier.citationMatrix Graph Grammars 2008-01,en_US
dc.identifier.urihttp://hdl.handle.net/10150/105736-
dc.description.abstractIf the aim of this dissertation had to be summarized in a single sentence, it could be algebraization of graph grammars. An equivalent one would be study of graph dynamics. From the point of view of a computer scientist, graph grammars are a natural generalization of Chomsky grammars for which a purely algebraic approach does not exist up to now. A Chomsky (or string) grammar is, roughly speaking, a precise description of a formal language (which in essence is a set of strings). On a more discrete mathematical style, it can be said that graph grammars â Matrix Graph Grammars in particular â study dynamics of graphs. Ideally, this algebraization would enforce our understanding of grammars in general, providing new analysis techniques and generalizations of concepts, problems and results known so far. In this dissertation we fully develop such theory over the field GF(2) which covers all graph cases, from simple graphs (more attractive for a mathematician) to multidigraphs (more interesting for an applied computer scientist). The theory is presented and its basic properties demonstrated in a first stage, moving to increasingly difficult problems and establishing relations among them.en_US
dc.format.mimetypeapplication/pdfen_US
dc.language.isoenen_US
dc.subjectComputer Scienceen_US
dc.subject.othergraph dynamicsen_US
dc.subject.othergraph grammarsen_US
dc.titleMatrix Graph Grammarsen_US
dc.typeThesisen_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.