We discuss simple functional transductions defined by invertible Mealy automata under iteration and in particular the question when the orbit relation defined by iteration is rational. We identify a class of these automata that has relatively complicated orbits, yet some of them are still orbit rational and discuss a number of decision problems associated with these devices.

Cellular automata have rich computational properties and, at the same time, provide plausible models of physics-like computation. We study decidability issues in the phasespace of these automata, construed as automatic structures over infinite words.

CDM, for computational discrete mathematics, is a course that attempts to teach a number of topics in discrete mathematics to computer science majors. The course abandons the classical definition-theorem-proof model, and instead relies heavily on computation as a source of motivation and also for experimentation and illustration. The emphasis on computational issues is particularly attractive to computer science majors and increases their involvement and participation.

Two algorithms are proposed to solve a reachability problem among time-dependent obstacles in 1D space. In the first approach, the motion planning problem is reduced to a path existence problem in a directed graph. The algorithm is very simple, with running time O(n/sup 2/), where n is the complexity of obstacles in space-time. The second algorithm uses a sweep-line technique and has running time O(n log/sub 2/ n). Besides, the latter algorithm can be easily modified to compute a collision-free trajectory, if such trajectories exist.

No abstract available.

Abstract The residual network reliability concerns networks with perfect edges and nodes that fail independently. It measures the probability that the network's operating nodes remain connected. The Assignment Problem deals with allocating given operating probabilities to the nodes of the network in such a way that the resulting residual network reliability is maximized. in this paper, we show that the Assignment Problem is computationally hard even for the restricted class of split networks, a generalization of threshold networks for which the problem is solvable in polynomial time.

This paper considers a probabilistic network in which the edges are perfectly reliable but the nodes fail with some known probabilities. The network is in an operational state if the surviving nodes induce a connected graph. The residual node connectedness reliability $R(G)$ of a network G is the probability that the graph induced by the surviving nodes is connected. This reliability measure is very different from the widely studied K-terminal network reliability measure. It is proven that the problem of computing the residual connectedness reliability is NP-hard by showing that the problem of counting the number of node induced connected subgraphs of a given graph is $# {\bf P}$-complete. The problem remains $# {\bf P}$-complete for split graphs as well as planar and bipartite graphs.

Abstract Let β be an arbitrary limit ordinal. A β-r.e. set is l-finite iff all its β-r.e. subsets are β-recursive. The l-finite sets correspond to the ideal of finite sets in the lattice of r.e. sets. We give a characterization of l-finite sets in terms of their ordertype: a β-r.e. set is l-finite iff it has ordertype less than β*, the Σ1, projectum of β).