1993 • 299 Pages • 67.19 MB • English

Posted April 14, 2020 • Uploaded
by kristina.larson

PREVIEW PDF

Page 1

^ L G E B R A l C ^ f f i U C T O E S LNJPATAAND ^ DATABASES JHEORY r^J World Scientific

Page 2

This page is intentionally left blank

Page 3

This page is intentionally left blank

Page 4

This page is intentionally left blank

Page 5

ALGEBRAIC STRUCTURES IN AUTOMATA AND DATABASES THEORY

Page 6

This page is intentionally left blank

Page 7

ALGEBRAIC STRUCTURES IN AUTOMATA AND DATABASES THEORY B I Plotkin L Ja Greenglaz Riga Aviation University, USSR A AGvaramija Abhazian State University, USSR World Scientific ™ b Singapore • New Jersey • London • Hong Kong

Page 8

Published by World Scientific Publishing Co. Pte. Ltd-. P O Box 128, Farrer Road, Singapore 9128 USA office: Suite IB, 1060 Main Street, River Edge, NJ 07661 UK office: 73 Lynton Mead, Totteridge, London N20 8DH ALGEBRAIC STRUCTURES IN AUTOMATA AND DATABASES THEORY Copyright © 1992 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording orany information storage and retrieval system now known or to be invented, without written permission from the Publisher. ISBN 981-02-0936-3 Printed in Singapore.

Page 9

V PREFACE This book i s devoted to the i n v e s t i g a t i o n of algebraic structures whispered by the concept of automaton. The emphasis i s made on algebraic framework of r e a l automata and databases. Thus, these notions appear as many-sorted algebraic st r u c t u r e s , allowing developed algebraic theory. Since t r e a t i n g of algebraic stru c t u r e paves way to the str u c t u r e and behavior of re a l automata and databases, we hope that the constructed theory w i l l f i n d i t s a p p l i c a t i o n s . On the other hand, we have pursued qu i t e a l o t of algebraic purposes, searching f o r ways of enriching algebra i t s e l f . This book consists of f i v e chapters. F i r s t four of them are re l a t e d d i r e c t l y to the algebraic theory of automata while the l a s t one, describing an algebraic model of database, takes a special pa r t . Nevertheless, t h i s chapter i s closely connected w i t h previous ones and we thi n k that t h i s book owns a c e r t a i n u n i t y . In both cases of automata and databases, we concentrate on mathematical models of the corresponding systems. This book i s addressed p r i m a r i l y f o r mathematicians graduates, postgraduates and conceivably f o r programmers, engineers and s c i e n t i s t s who wish to apply algebraic methods i n t h e i r research. We have t r i e d to minimize the algebraic background of the p o t e n t i a l reader, therefore the d e f i n i t i o n s i n the "Preliminary notions" and i n the sequel attempt to make the book self-contained. However, touching the advanced top i c s , we assume a c e r t a i n f a m i l i a r i t y w i t h universal algebra, theory of groups and semigroups. Chapter 5 w i l l be much easier f o r those who are acquainted w i t h s e t - t h e o r e t i c a l and l o g i c a l methods. The concept of automaton arises i n various problems associated wi t h computer science, network systems, cont r o l theory etc. I t s mathematical st r u c t u r e i s based on i n t u i t i v e arguments, r e f l e c t i n g the e n t i t y of r e a l (not necessarily physical) automata. Now, automata theory i s a developed mathematical f i e l d . On our opinion, two aspects could be pointed out i n automata research. They are the combinatorial approach

Page 10

vi and algebraic theory. The f i r s t one ( [ 3 8 ] , [5 4 ] , [99] etc.) i s i n a greater extent connected with behavior, analysis and synthesis of automata. Ce r t a i n l y , both these d i r e c t i o n s are not mutually independent: algebraic methods are used i n combinatorial problems. For example, algebraic automata theory plays a s i g n i f i c a n t ro l e i n the theory of algorithms and languages ( [ 3 7 ] , [ 3 8 ] ) . However, speaking on algebraic aspect of automata theory, f i r s t of a l l we bear i n mind an automaton as an algebraic structure ( t h i s point of view has been r e f l e c t e d i n [ 2 9 ] , [ 3 4 ] , [2] e t c . ) . A consequent analysis of t h i s algebraic s t r u c t u r e i s one of the main goals of t h i s book. Moreover, the algebraic s t r u c t u r e of automaton provides an important information about the s t r u c t u r e of r e a l automata. Krohn-Rhodes decomposition Theorem turns out to be the most impressive witness of t h i s . Another important d i r e c t i o n i s presented by ap p l i c a t i o n of algebraic methods f o r the c l a s s i f i c a t i o n of automata, descript i o n of i t s behavior by i d e n t i t i e s , study of v a r i e t i e s of automata. That i s why the standard algebraic notions: automorphisms, i d e n t i t i e s and v a r i e t i e s are widely used i n t h i s book. F i n a l l y , we have t r i e d to fol l o w the categorical point of view on automaton as on algebraic systems. As i t was mentioned, chapter 5 i s meant f o r the construction of adequate algebraic model of databases. This theme i s studied i n d e t a i l i n the book of B. P l o t k i n ([ 8 6 ] ) and we freq u e n t l y r e f e r to i t . I n t h i s chapter, we describe the sketch of the theory. A number of problems i n the theory of r e l a t i o n a l databases can be reformulated i n terms of an algebraic model. Among them are the problems of informational equivalence and isomorphism of databases, i t s composition and decomposition, c l a s s i f i c a t i o n on the base of symmetries and so on. An automaton s£=(A,X,B) i s an algebraic system w i t h three basic sets, A, X, B call e d the sets of sta t e s , input signals and output signals respectively, and two binary operations: o : AxX —> A, * : AxX —> B. The operation ° i s a fu n c t i o n of two variables asA, xeX, whose values l i e i n the set of states A: a°x = a' € A. I t i s of t e n c a l l e d a

Automata-2008: Theory and Applications of Cellular Automata

2008 • 636 Pages • 14.97 MB

Automata Theory with Modern Applications

2006 • 265 Pages • 1.57 MB

Automata, Computability and Complexity: Theory and Applications

2007 • 1124 Pages • 109.61 MB

Theory of Computer Science (Automata, Languages and Computation) Third Edition

2010 • 434 Pages • 16.85 MB

An Introduction to Formal Languages and Automata, 5th Edition

2011 • 532 Pages • 8.53 MB

Permissive strategies in timed automata and games

2015 • 18 Pages • 1.98 MB

Logic, Automata, and Algorithms

1971 • 444 Pages • 5.16 MB

Logic, Automata, and Algorithms

1971 • 444 Pages • 15.77 MB

Topics in the General Theory of Structures

1987 • 209 Pages • 10.71 MB

Data Structures and Algorithms Made Easy: Data Structures and Algorithmic Puzzles

2017 • 828 Pages • 32.74 MB

Automata Old and New by Conrad William Cooke

2021 • 32 Pages • 277.93 KB

Verification of timed automata: reachability, liveness, and modeling

2016 • 174 Pages • 4.34 MB

Algebraic Methods II: Theory, Tools and Applications

1991 • 430 Pages • 23.2 MB

Data Structures and Algorithms in Java

2013 • 738 Pages • 9.94 MB

Data Structures and Algorithms in C++ 2e

2011 • 738 Pages • 17.02 MB

Database Reengineering and Interoperability

1996 • 351 Pages • 11.11 MB