Comparing Entire Prototypes at Semigroup Homomorphisms and Specifically at Regular Languages Substitutions

The following statements are proven: A correspondence of a semigroup in another one is a homomorphism if and only if when the entire prototype of the product of images contains (always) the product of their entire prototypes. The Kleene closure of the maximal rewriting of a regular language at a regular language substitution contains in the maximal rewriting of the Kleene closure of the initial regular language at the same substitution. Let the image of the maximal rewriting of a regular language at a regular language substitution covers the entire given regular language. Then the image of any word from the maximal rewriting of the Kleene closure of the initial regular language covers by the image of a set of some words from the Kleene closure of the maximal rewriting of this given regular language everything at the same given regular language substitution. The purposefulness of the ¯rst statement is substantiated philosophically and epistemologically connected with the spirit of previous mathematical results of the author. A corollary of its is indicated about the membership problem at a regular substitution.

Conceptual Information Compression and Efficient Pattern Search

This paper introduces an encoding of knowledge representation statements as regular languages and proposes a two-phase approach to processing of explicitly declared conceptual information. The idea is presented for the simple conceptual graphs where conceptual pattern search is implemented by the so called projection operation. Projection calculations are organised into off-line preprocessing and run-time computations. This enables fast run-time treatment of NP-complete problems, given that the intermediate results of the off-line phase are kept in suitable data structures. The experiments with randomly-generated, middle-size knowledge bases support the claim that the suggested approach radically improves the run-time conceptual pattern search.