Modeling a complicated system as a multi-agent system is one of the most promising ways of designing a large, complex system. If we can assume that each agent in a multi-agent system has mental states (beliefs, knowledge, desires and so on), we can formalize each agent's behaviors in an abstract way without being bothered by system implementation details. We present semantic structures that are useful for representing belief states in multi-agent environments. One of the structures is a restriction of partial Kripke structures studied by Jaspars and Thijsse: we assume that each agent can access from a state of a structure to at most one state. We call the restricted structures only-child partial Kripke structures. We show some properties of only-child partial Kripke structures. Another structure is a restriction of the alternate nonstandard structures defined by Fagin et al. to deal with the logical-omniscience problem. We show several relationships between partial Kripke structures and the restriction of alternate nonstandard structures. Using the results, we show that the outputs of a belief estimation algorithm we previously developed can be characterized by using only-child partial Kripke structures. Finally, we show that only-child partial Kripke structures are more appropriate for the belief estimation problem than the restricted nonstandard structures.

In database normalization theory, multivalued dependencies (MVDs) play an important and much-studied role. However, their semantic aspects in a conceptual schema have not been so thoroughly studied. This is one of the causes which prevent the theory from being applied to actual database design. This paper clarifies that, in a conceptual schema, MVDs have at least two different meanings. In this paper we first define a data model, called a functional dependency graph. We show that a relation scheme can be constructed from the functional dependency graph. Then, we show that MVDs which hold in the relation scheme correspond to certain substructures of the functional dependency graph. This is one meaning of MVDs. Another meaning of MVDs is that MVDs are embodied by unions of relations having different relation schemes. We show that a semantic problem with transitively specified MVDs does not arise when we interpret MVDs to have the latter meaning. It becomes easier to obtain MVDs from out real world by using the results just described. This helps us apply database normalization theory to actual database design.

In this paper, we propose a fast signature scheme which realizes short transmissions and minimal on-line computation. Our scheme requires a modular exponentiation as preprocessing (i.e., off-line computation). However, we need to acknowledge the existance of the following remarkable properties: neither multiplication nor modular reduction is used in the actual signature generation (i.e., on-line computation). Our scheme requires only two operations: hashing and addition. Although some fast signature schemes with small on-line computation have been proposed so far, those schemes require multiplication or modular reduction in the on-line phase. This leads to a large amount of work compared to that of addition. As far as we know, this is the first approach to obtain the fast signature without those two calculus methods.

This paper concerns cancel minimal linear grammars ([5]) that was introduced to generalize Geffert normal forms for phrase structure grammars. We consider the generative power of restricted cancel minimal linear grammars: the grammars have only one nonterminal symbol C except the start symbol S, and their productions consist of context-free type productions, the left-hand side of which is S and the right-hand side contains at most one occurrence of S, and a unique cancellation production Cm ε that replaces the string Cm by the empty string ε. We show that, for any given positive integer m, the class of languages generated by cancel minimal linear grammars with Cm ε, is properly included in the class of linear languages. Conversely, we show that for any linear language L, there exists some positive integer m such that a cancel minimal linear grammar with Cm ε generates L. We also show how the generative power of cancel minimal linear grammars with a unique cancellation production Cm ε vary according to changes of m and restrictions imposed on occurrences of terminal symbols in the right-hand side of productions.