Graph Algebras and AutomataCRC Press, 8 de jul. de 2003 - 344 páginas Graph algebras possess the capacity to relate fundamental concepts of computer science, combinatorics, graph theory, operations research, and universal algebra. They are used to identify nontrivial connections across notions, expose conceptual properties, and mediate the application of methods from one area toward questions of the other four. After a concentrated review of the prerequisite mathematical background, Graph Algebras and Automata defines graph algebras and reveals their applicability to automata theory. It proceeds to explore assorted monoids, semigroups, rings, codes, and other algebraic structures and to outline theorems and algorithms for finite state automata and grammars. |
Conteúdo
Preface | 1 |
Algebraic Structures | 39 |
Automata and Languages | 143 |
Syntactic Monoids of Automata | 219 |
Congruences on Automata | 227 |
Minimal Automata | 249 |
Languages | 255 |
Tree Languages | 283 |
Equational Theories | 289 |
Groupoid Rings | 311 |
Open Problems | 321 |
Bibliography | 329 |
351 | |
Outras edições - Ver todos
Termos e frases comuns
A₁ Alg(G algorithm alphabet Atme D,T automata automaton Atm belongs binary called Cayley graph Cayley table codewords Compute congruence connected component contains Contq(x defined definition denoted direct product disjoint divisors edges encoding equal equations equivalence relation Example Exercise exists extended Euclidean algorithm Figure Find finite state automaton go e1 go eo go go go graph algebra Alg(D groupoid Hence homomorphism implies in-closed subset In(a In(b induced induced subgraph isolated vertex isomorphic Kelarev labeled language accepted language recognized lattice Lemma mapping minimal automaton monoid multiplication Nerode equivalence nonempty nonzero notation operations parity-check matrix permutation polynomial positive integers quotient r₁ Rees matrix semigroup regular expression ring row-echelon form satisfies semilattice Solution subgraph subgroup subsemigroup Suppose syntactic monoid syntactic semigroup t₁ Theory transition diagram undirected graph vectors verify vertices word