Artificial
Social Systems
Y.
Moses, M. Tenneholtz
Abstract.
An artificial social system is a set
of restrictions of agents' behaviors in a multi-agent environment. Its role is
to allow agents to coexist in a shared environment and pursue their respective
goals in the presence of other agents. This paper argues that artificial social
systems exist in practically every multi-agent system, and play a major role in
the performance and effectiveness of the agents. We propose artificial social
systems as an explicit and formal object of study, and investigate several basic
issues that arise in their design.
Controlling
the Consumption of Storage with Sliding Priority Search in a Hyper-Linking Based
Theorem Prover
S.-J-
Lee, D.A. Plaisted
Abstract.
The hyper-linking strategy
proposed in [17] eliminates duplication of instances of clauses during the
process of inference. However, hyper/instances were generated exhaustively by
breadth/first search which may cause memory-paging troubles for hard problems
since all hyper-instances have to be stored and processed. We present a sliding
priority search to provide control on the number of hyper-instances saved and
the amount of memory consumed by discarding those instances whose priority value
exceeds a priority bound. The bound is set automatically rather than by the
user. A technique similar to iterative deepening is also applied to preserve
completeness of the hyper-linking strategy. The sliding priority method enabled
us to get a number of proofs that could not be obtained with breadth-first
search.
Automated
Transformation of Sequential Divide-And-Conquer Algorithms into Parallel
Programs
B.
Freisleben, T. Kielmann
Abstract.
Divide-and-conquer algorithms obtain the solution to a given problem by dividing
it into subproblems, solving these recursively and combining their solutions. In
this paper we present a system that automatically transforms sequential
divide-and-conquer algorithms written in the C programming language into
parallel code which is then executed on message-passing multicomputers. The user
of the system is expected to add only a few annotations to an existing
sequential program. The strategies required for transforming sequential source
code to executable binaries are discussed. The performance speedups attainable
will be illustrated by several examples.
Sequential
and Parallel Approximate Convex Hull Algorithms
Ch.E.
Kim, I. Stojmenovič
Abstract.
This paper defines the area measure of the quality of approximate convex hulls
and proposes two new approximate convex hull algorithms. The first one is
superior to known
techniques under the area measure and comparable under the distance
measure and time complexity. The second algorithm is superior to all known
algorithms in both area and distance measures (including the first algorithm)
while having slightly higher time complexity. Corresponding parallel algorithms
for finding approximate convex hull are also described.
On
Varieties of Density and Crossing Properties for Event Structures
V.E.
Kotov, S.A. Starkova, I.B. Virbitskaite
Abstract.
We study prime event structures as models for nondeterministic processes and
some of their properties known as discreteness, density and crossing. These
properties allow inconsistency to be avoided between syntactic and semantic
representations of processes. A number close relationships between different
density and crossing concepts is established. It has turned out that in an
M-dense event structure all of the executions are completely
"successful" (i.e. at least one successor (if it exists) for
any event occurring in the execution must also occur).