Narrow Results

This paper deals with two topics concerning two-dimensional automata operating in parallel. We first investigate a relationship between the accepting powers of two-dimensional alternating finite automata (2-AFAs) and nondeterministic bottom-up pyramid cellular acceptors (NUPCAs), and show that Ω (diameter × log diameter) time is necessary for NUPCAs to simulate 2-AFAs. We then investigate space complexity of two-dimensional alternating Turing machines (2-ATMs) operating in small space, and show that if L (n) is a two-dimensionally space-constructible function such that lim_{n → ∞} L (n)/loglog n > 1 and L (n) ≤ log n, and L′ (n) is a function satisfying L′ (n) =o (L(n)), then there exists a set accepted by some strongly L (n) space-bounded two-dimensional deterministic Turing machine, but not accepted by any weakly L′ (n) space-bounded 2-ATM, and thus there exists a rich space hierarchy for weakly S (n) space-bounded 2-ATMs with loglog n ≤ S (n) ≤ log n.

This paper introduces a cooperating system of three-way, two-dimensional finite automata (CS-TR2-FA) which is a restricted version of a cooperating system of four- way, two-dimensional finite automata (CS-2-FA), and mainly investigates several fundamental properties of this system as a two-dimensional language acceptor whose input tapes are restricted to square ones. We show that

(1) CS-TR2-FA’s are equivalent in accepting power to three-way, two-dimensional simple multihead finite automata,

(2) CS-2-FA’s are more powerful than CS-TR2-FA’s,

(3) £[CS-TR2-DFA(k)^S] ⊊ £[CS-TR2-NFA(k)^S],

(4) ⋃_1≤k<∞ £[CS-TR2-DFA(k)^S] ⊊ ⋃_1≤k<∞ £[CS-TR2-NFA(k)^S], and

(5) £[CS-TR2-DFA(k)^S] (£[CS-TR2-NFA(k)^S]) ⊊ £[CS-TR2-DFA(k+1)^S] (£[CS-TR2-NFA(k+1)^S]),

where £[CS-TR2-DFA(k)^S] (£[CS-TR2-NFA(k)^S]) denotes the class of sets of square input tapes accepted by CS-TR2-FA’s which consist of k deterministic (non-deterministic) finite automata.

Hard discrete optimization problems using randomized methods such as genetic algorithms require large numbers of samples from the solution space. Each candidate sample/solution must be evaluated using the target fitness/energy function being optimized. Such fitness computations are a bottleneck in sampling methods such as genetic algorithms. We observe that the caching of partial results from these fitness computations can reduce this bottleneck. We provide a rigorous analysis of the run-times of GAs with and without caching. By representing fitness functions as classic Divide and Conquer algorithms, we provide a formal model to predict the efficiency of caching GAs vs. non-caching GAs. Finally, we explore the domain of protein folding with GAs and demonstrate that caching can significantly reduce expected run-times through both theoretical and extensive empirical analyses.

This paper presents a system based on new operators for handling sets of propositional clauses compactly represented by means of ZBDDs. The high compression power of such data structures allows efficient encodings of structured instances. A specialized operator for the distribution of sets of clauses is introduced and used for performing multiresolution on clause sets. Cut eliminations between sets of clauses of exponential size may then be performed using polynomial size data structures. The ZRES system, a new implementation of the Davis-Putnam procedure of 1960, solves two hard problems for resolution, that are currently out of the scope of the best SAT provers.

Possibilistic graphical models are powerful modeling and reasoning tools for uncertain information based on possibility theory. In this paper, we provide an analysis of computational complexity of MAP and MPE queries for possibilistic networks. MAP queries stand for maximum a posteriori explanation while MPE ones stand for most plausible explanation. We show that the decision problems of answering MAP and MPE queries in both min-based and product-based possibilistic networks is NP-complete. Definitely, such results represent an advantage of possibilistic graphical models over probabilistic ones since MAP queries are NP^PP -complete in Bayesian networks. Our proofs for querying min-based possibilistic networks make use of reductions from the 3SAT problem to querying possibilistic networks decision problem. Moreover, the provided reductions may be useful for the implementation of MAP and MPE inference engines based on the satisfiability problem solvers. As for product-based networks, the provided proofs are incremental and make use of reductions from SAT and its weighted variant WMAXSAT.

Computation and decision problems related to argumentation frameworks with higher-order attacks have not received a lot of attention so far. This paper is a step towards these issues. First, it provides a labelling counterpart for the structure semantics of Recursive Argumentation Frameworks (RAF). Second, it investigates the complexity of decision problems associated with RAF. This investigation shows that, for the higher expressiveness offered by these enriched systems, the complexity is the same as for classical argumentation frameworks. As a side contribution, a new semantics for RAF, the semi-stable semantics, and a new process for translating RAF into Argumentation Frameworks without higher-order attacks (AF), are introduced. Finally, new notions which are the counterparts of equivalent notions already existing for AF (among them, the Strongly Connected Components — SCC) are defined and investigated in order to involve them in the future development of algorithms for computing RAF labelling semantics.

Using high-level tasks typical of managerial decisions, this experimental study examined the influence of computer assistance on solving ill-structured problems. Of specific interest were the influences of complex and simple assistance on decision performance and decision maker attitudes. Our findings suggest that performance and user attitudes can be enhanced by technology that provides clear and simple instruction in good problem-solving practices. However, when that technology adds a complex array of technical options and features, the assistance may fail to improve or/and may even diminish performance and damage user attitudes. Familiarization with such complex technology may not improve these outcomes. The findings regarding the relationship between assistance complexity and decision performance are consistent with those of studies that suggest complexity has a curvilinear influence on performance. When considering the application of technological assistance to ill-structured decision tasks, the complexity of the assistance should not be ignored.

Of all the issues discussed at Alife VII: Looking Forward, Looking Backward, the issue of whether it was possible to create an artificial life system that exhibits open-ended evolution of novelty is by far the biggest. Of the 14 open problems settled on as a result of debate at the conference, some 6 are directly, or indirectly related to this issue.

Most people equate open-ended evolution with complexity growth, although a priori these seem to be different things. In this paper I report on experiments to measure the complexity of Tierran organisms, and show the results for a size-neutral run of Tierra. In this run, no increase in organismal complexity was observed, although organism size did increase through the run. This result is discussed, offering some signposts on path to solving the issue of open ended evolution.

In this context, a model is an algorithm or a procedure that applies to data resulting in a functional relation τ between “input space” $\mathcal{X}$ and “output space” $\mathcal{Y}$. In this short paper, we will delineate objective criteria which help to disambiguate and rate models’ credibility. We will define pertinent concepts and will voice an opinion on the matter of good versus bad versus so–so models.