A method is proposed for constructing multiway gateways to interconnect several local area networks (LANs) or wide area networks (WANs) and provide gateway services among them. A multiway gateway accommodates intercommunications between networks whose subnet protocols may differ and whose locations may be geographically dispersed, and has advantages of flexibility and efficiency. The proposed approach uses the concept of remote gateways, in which the functionality of a gateway is partitioned into two separate modules (local and remote), and a dedicated communication link connects these two parts. A description is given of the concept of a remote gateway and the approach used to construct multiway gateways based on them. The design issues for a multiway gateway and possible applications to network management are also addressed.>

A deduction graph (DG) for logically deducing a new functional dependency (FD) or function-free Horn formula (extended from Horn clauses) from a subset of a given FDs or function-free headed Horn clauses in a relational database or rule-based expert systems is defined. An algorithm with a polynomial time complexity for constructing a DG based on a number of rules is designed. Applications of DGs to relational databases, rule-based expert systems, logic programming, and artificial intelligence are investigated. In addition to graphically solving the inference problem by DGs, many logic queries can be answered by DGs with substitutions for unifying expressions.>

Two algorithms for constructing minimal deduction graphs (MDG) for inferring rules and facts in an extended version of the Horn clause logic are described. A deduction graph (DG) is minimal if the number of arcs in the graph is minimized. Horn clauses (HC) are extended to Horn formulas (HF), such that the head or the body of an HF can be a conjunction of positive literals or a disjunction of the bodies of some rule instances, respectively. Each algorithm constructs an MDG from its source to its sink, whose arcs infer the HF 'if source then sink'. The construction of an MDG is based on a sound and complete set of inference rules of reflexivity, transitivity, and conjunction for HFs which proceeds by expanding a tree rooted at its sink until its source has a successful backtracking to the root. Then the MDG is extracted from the tree. The nodes being expanded in such a tree are classified into seven types, which are assigned by different priorities for their growing into subtrees or for their pruning to reduce the tree space.>

An algorithm for synthesizing a better relational database scheme in elementary key normal form (EKNF) is developed. This algorithm eliminates not only extraneous attributes and other redundancies, but also superfluities from a given set of functional dependences (FDs), based primarily on subset closures, Hamiltonian cycles of FDs, and equivalent subsets of attributes. Following this algorithm, a better LR-minimum FD covering is obtained. A more practical and efficient method for designing a relational database scheme in EKNF is then provided. The time complexity of the algorithm is polynomial.>

This paper shows that many production rules in a rule based system and some functional dependencies in a relational database can be transformed into Horn clauses. This paper also develops an algorithm for constructing a more general deduction graph that is extended from the algorithm in Ref. 12, originally designed for finding a subset of functional dependencies, which logically deduces a functional dependency not in the subset. Since a relational database is a special case of a logic program5, many existing techniques in the area of relational databases can be extended and then used in logic programming and particularly in the Horn clause logic queries without relying on the resolution-refutation theorem-proving method in artifical intelligence. By using this new graphical method, there are several advantages as compared with the standard PROLOG implementation.

For the given directed graphs, a method based on Moore sequential machines (MSM) for solving the graph isomorphism problem was recently proposed. However, that method provides only a necessary (but not a sufficient) condition. This correspondence corrects this error by developing a necessary and sufficient condition. It will be shown that this type of problem can be also solved by using deterministic state machines (DSM). But there are tradeoffs to be considered in using either DSM's or MSM's. In addition, the effectiveness of the method based on MSM's depends very much on the output definition.

This correspondence proposes a new algorithm for deriving all pairs of compatible and incompatible states of any incompletely or completely specified sequential machine. The method needs a single step in checking the contents of the closure classes with respect to each pair of distinct states. A working example is given for illustrating the method by hand computation. The algorithm is implemented by a PL/I program and executed by using the incomplete machine of the example as input data on an IBM system 370/Model 158. These demonstrations assure that the algorithm is feasible and efficient for both hand computation and computer execution.

This correspondence provides an extended version of the algebraic method using Boolean algebra for deriving all maximal compatibles. It then shows that the algorithm based on the reduction of the edge-inclusion table, with respect to a given incompatibility graph for finding all maximal compatibles, is equivalent to the extended version just mentioned, and that the latter is much simpler.

The transition preserving morphisms (endomorphism, homomorphism, isomorphism, and automorphism) of state machines are developed on the basis of nontrivial closed partitions over their state sets. Algorithms with illustrated examples are provided for determining these morphisms. By means of these morphisms, the structural preserving morphisms of finite automata can be readily solved by simply making a constraint on each partition being not only nontrivial and closed but also output-consistent.

This correspondence provides some clarifications and revision to the above-mentioned paper.1 It also presents the generalized versions of the definitions and theorems related to closure classes. These versions are applicable to arbitrary subsets of the state set of a sequential machine.

This correspondence provides theorems for the existence of a nontrivial closed parition on the state set of a sequential machine and offers an efficient and systematic method for generating all such partitions. The method is based on the concept of the implication or closure dependence relation among some subsets of the state set.

A new method based on a closure partition over a set of some compatibles is proposed for selecting a minimal machine from mutualy independent closure aggregates by simply checking only the trivial covering condition. The closure aggregates are derived from some closure related classes. The latter classes are derived from the closure classes by replacing aU superseded elements with their greatest superseding ones. The compatibles to be considered are some subsets of maximum compatibles related under the state transition or the set inclusion. Closure dependent classes may contain superseded and redundant compatibles but their corresponding closure aggregates have only unsuperseded and irredundant elements. Both of them are closed. However, some closure related class may not be closed and may contain some redundant elements. The remaining unrelated subsets of maximum compatibles are ignored. Superseded or redundant compatibles when they are so determined are also ignored. Thus possible candidates for irredundant closed covers can be yielded and then partitioned under the closure dependence relation.