Search

Abstract: We study the derivational complexities of string rewriting systems. We discuss the following fundamental question: which functions can be derivational complexities of terminating finite string rewriting systems? They are recursive, but for any recursive function, there is a derivational complexity larger than it. We relate them to the time functions of Turing machines. In particular, we show that the functions and for a real number are equivalent to the derivational complexity of some finite string rewriting systems if the computational complexity of is relatively low (for example, is rational, algebraic, or ). On the other hand, they cannot be equivalent to any derivational complexities if the complexity of is high. [Copyright &y& Elsevier]

Abstract: In this paper, we consider insertion–deletion P systems with priority of deletion over insertion. We show that such systems with one-symbol context-free insertion and deletion rules are able to generate Parikh sets of all recursively enumerable languages (). If a one-symbol one-sided context is added to the insertion or deletion rules, then all recursively enumerable languages can be generated. The same result holds if a deletion of two symbols is permitted. We also show that the priority relation is very important, and in its absence the corresponding class of P systems is strictly included in the family of matrix languages (). [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate various decision problems concerning parameterized versions of some classes of machines. Let be the class of nondeterministic multitape Turing machine (TM) acceptors with a two-way read-only input, at most states, at most read–write worktapes, and at most symbols in the worktape alphabet, where are fixed positive integers. There is no restriction on the cardinality of the input alphabet. We are able to show the emptiness, disjointness, and universe (also called universality) problems to be decidable for . For the class consisting of machines in that always halt or whose minimal-time accepting computations can be bounded by some recursive function (where is the input length), the containment and equivalence problems are decidable. These results hold for other machines, e.g., when the worktapes are pushdown stacks (where on every step, each pushdown can only pop the top of the stack or replace the top of the stack by at most two symbols) or when stacks are counters (where on every step, a counter can be incremented by 1, decremented by 1, or remain unchanged, and can be tested for zero). Our results are the best possible in the sense that not parameterizing one of (or, in the case of counter machines, allowing the counters to increment by arbitrary integers that may change from machines to machines) makes the universe problem undecidable. We also give a simple characterization of the languages defined by . Finally, we investigate the applicability of our techniques to machines with multiple input heads or multiple input tapes. [Copyright &y& Elsevier]

Abstract: Being motivated by John Tantalo’s Planarity Game, we consider straight line plane drawings of a planar graph with edge crossings and wonder how obfuscated such drawings can be. We define , the obfuscation complexity of , to be the maximum number of edge crossings in a drawing of . Relating to the distribution of vertex degrees in , we show an efficient way of constructing a drawing of with at least edge crossings. We prove bounds for an -vertex planar graph with minimum vertex degree . The shift complexity of , denoted by , is the minimum number of vertex shifts sufficient to eliminate all edge crossings in an arbitrarily obfuscated drawing of (after shifting a vertex, all incident edges are supposed to be redrawn correspondingly). If , then is linear in the number of vertices due to the known fact that the matching number of is linear. However, in the case we notice that can be linear even if the matching number is bounded. As for computational complexity, we show that, given a drawing of a planar graph, it is NP-hard to find an optimum sequence of shifts making crossing-free. [Copyright &y& Elsevier]

Abstract: Many attempts to transcend the fundamental limitations to computability implied by the Halting Problem for Turing Machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. Thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. Here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability. [Copyright &y& Elsevier]

Abstract: The two determinization procedures of Safra and Muller–Schupp for Büchi automata are compared, based on an implementation in a program called OmegaDet. [Copyright &y& Elsevier]

Abstract: This paper proves the decidability of several problems in the theory of HD , and PD systems, some of which that have been proved before but are now proved in a different way. First, the paper tackles the decidability of the nilpotency of HD systems and the infinitude of PD languages. Then, we prove the decidability of the problem of momentary stagnation of the growth function of PD systems. Finally, we suggest a way to solve the decidability of the momentary stagnation of the growth function of systems, proving the decidability of the infinitude of HD as a trivial consequence. [Copyright &y& Elsevier]

Stream X-machines are a formalisation of extended finite state machines that have been used to specify systems. One of the great benefits of using stream X-machines, for the purpose of specification, is the associated test generation technique which produces a test that is guaranteed to determine correctness under certain design for test conditions. This test generation algorithm has recently been extended to the case where the specification is non-deterministic. However, the algorithms for testing from a non-deterministic stream X-machine currently have limitations: either they test for equivalence, rather than conformance or they restrict the source of non-determinism allowed in the specification. This paper introduces a new test generation algorithm that overcomes both of these limitations, for situations where the implementation is known to be deterministic. [Copyright &y& Elsevier]

Let K be the two-dimensional grid. Let q be an integer greater than 1 and let Q={0,…,q-1}. Let s : Q→Q be defined by s(α)=(α+1) mod q, ∀α ∈ Q.In this work we study the following dynamic F on QZ2. For x ∈ QZ2 we define Fv(x)=s(xv) if the state s(xv) appears in one of the four neighbors of v in K and Fv(x)=xv otherwise.For x ∈ QZ2, such that {v∈Z2 : xv ≠ 0} is finite we prove that there exists a finite family of cycles such that the period of every vertex of K divides the lcm of their lengths. This is a generalization of the same result known for finite graphs. Moreover, we show that this upper bound is sharp. We prove that for every n⩾1 and every collection k1,…,kn of non-negative integers there exists yn ∈ QZ2 such that |{v∈Z2 : ynv ≠ 0}| = O(k12+⋯+kn2) and the period of the vertex (0,0) is p·lcm{k1,…,kn}, for some even integer p. [Copyright &y& Elsevier]

A survey of the field of hypercomputation, including discussion of four a priori objections to the possibility of hypercomputation. An exegesis of Turing''s pre- and post-war writings on the mind is given, and Turing''s views on the scope of machines are discussed. [Copyright &y& Elsevier]

We now know both that hypercomputation (or super-recursive computation) is mathematically well-understood, and that it provides a theory that according to some accounts for some real-life computation (e.g., operating systems that, unlike Turing machines, never simply output an answer and halt) better than the standard theory of computation at and below the “Turing Limit.” But one of the things we do not know is whether the human mind hypercomputes, or merely computes—this despite informal arguments from Gödel, Lucas, Penrose and others for the view that, in light of incompleteness theorems, the human mind has powers exceeding those of TMs and their equivalents. All these arguments fail; their fatal flaws have been repeatedly exposed in the literature. However, we give herein a novel, formal modal argument showing that since it''s mathematically possible that human minds are hypercomputers, such minds are in fact hypercomputers. We take considerable pains to anticipate and rebut objections to this argument. [Copyright &y& Elsevier]

Accelerating Turing machines are devices with the same computational structure as Turing machines (TM), but able to perform super-tasks. We ask whether performing super-tasks alone produces more computational power; for example, whether accelerating TM can solve the halting problem. We conclude that this is not the case. No accelerating TM solves the halting problem. The argument rests on an analysis of the reasoning that leads to Thomson''s paradox. The key point is that the paradox rests on a conflation of different perspectives of accelerating processes. This leads to concluding that the same conflation underlies the claim that accelerating TM can solve the halting problem. [Copyright &y& Elsevier]

The main purpose of this paper is to present a fast matrix multiplication algorithm taken from the paper of Laderman et al. (Linear Algebra Appl. 162–164 (1992) 557) in a refined compact “analytical” form and to demonstrate that it can be implemented as quite efficient computer code. Our improved presentation enables us to simplify substantially the analysis of the computational complexity and numerical stability of the algorithm as well as its computer implementation. The algorithm multiplies two N × N matrices using O(N2.7760) arithmetic operations. In the case where N = 18·48k, for a positive integer k, the total number of flops required by the algorithm is 4.894N2.7760−16.165N2, which may be compared to a similar estimate for the Winograd algorithm, 3.732N2.8074−5N2 flops, N = 8·2k, the latter being current record bound among all known practical algorithms. Moreover, we present a pseudo-code of the algorithm which demonstrates its very moderate working memory requirements, much smaller than that of the best available implementations of Strassen and Winograd algorithms. For matrices of medium-large size (say, 2000&les;N<10,000) we consider one-level algorithms and compare them with the (multilevel) Strassen and Winograd algorithms. The results of numerical tests clearly indicate that our accelerated matrix multiplication routines implementing two or three disjoint product-based algorithm are comparable in computational time with an implementation of Winograd algorithm and clearly outperform it with respect to working space and (especially) numerical stability. The tests were performed for the matrices of the order of up to 7000, both in double and single precision. [Copyright &y& Elsevier]

We introduce Concurrent Timed Automata (CTAs) where automata running in parallel are synchronized. We consider the subclasses of CTAs obtained by admitting, or not, diagonal clock constraints and constant updates, and by letting, or not, sequential automata to update the same clocks. We prove that such subclasses recognize the same languages but differ w.r.t. the succinctness of the models. Moreover, we distinguish between subclasses that are polynomially closed w.r.t. finite union and finite intersection, and subclasses that do not have such properties. [Copyright &y& Elsevier]