Fundamenta Informaticae - Volume 91, issue 2

Article Type: Other

DOI: 10.3233/FI-2009-0040

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. i-ii, 2009

Authors: Arrighi, Pablo | Fargetton, Renan | Wang, Zizhu

Article Type: Research Article

Abstract: We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any onedimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will then correspond to one step of the simulated QCA. The simulation preserves the topology in the sense that each cell of the simulated QCA is encoded as a …group of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration. Show more

Keywords: Quantum cellular automata, Intrinsic universality, Quantum computation

DOI: 10.3233/FI-2009-0041

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 197-230, 2009

Authors: Bertoni, Alberto | Goldwurm, Massimiliano | Lonati, Violetta

Article Type: Research Article

Abstract: In this paper we consider the classes REC1 and UREC1 of unary picture languages that are tiling recognizable and unambiguously tiling recognizable, respectively. By representing unary pictures by quasi-unary strings we characterize REC1 (resp. UREC1) as the class of quasi-unary languages recognized by nondeterministic (resp. unambiguous) linearly space-bounded one-tape Turing machines with constraint on the number of head reversals. We apply such a characterization in two directions. First we prove that the …binary string languages encoding tiling recognizable unary square languages lies between NTIME(2n) and NTIME(4n); by separation results, this implies there exists a non-tiling recognizable unary square language whose binary representation is a language in NTIME(4n log n). In the other direction, by means of results on picture languages, we are able to compare the power of deterministic, unambiguous and nondeterministic one-tape Turing machines that are linearly space-bounded and have constraint on the number of head reversals. Show more

Keywords: two-dimensional languages, tiling systems, linearly space-bounded Turing machine, head reversal-bounded computation

DOI: 10.3233/FI-2009-0042

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 231-249, 2009

Authors: Bliudze, Simon | Krob, Daniel

Article Type: Research Article

Abstract: We develop a unified functional formalism for modelling complex systems, that is to say systems that are composed of a number of heterogeneous components, including typically software and physical devices. Our approach relies on non-standard analysis that allows us to model continuous time in a discrete way. S ystems are defined as generalized Turing machines with temporized input, internal and output mechanisms. Behaviors of systems are represented by transfer functions. A transfer function is said …to be implementable if it is associated with a system. This notion leads us to define a new class – which is natural in our framework – of computable functions on (usual) real numbers. We show that our definitions are robust: on one hand, the class of implementable transfer functions is closed under composition; on the other hand, the class of computable functions in our meaning includes analytical functions whose coefficients are computable in the usual way, and is closed under addition, multiplication, differentiation and integration. Our class of computable functions also includes solutions of dynamical and Hamiltonian systems defined by computable functions. Hence, our notion of system appears to take suitably into account physical systems. Show more

Keywords: Complex system, Hybrid system, Non-standard analysis, Physical system, Software system, System modelling, Temporized systems, Time scale, Turing machine

DOI: 10.3233/FI-2009-0043

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 251-274, 2009

Authors: Bozga, Marius | Iosif, Radu | Lakhnech, Yassine

Article Type: Research Article

Abstract: In this paper we study the reachability problem for parametric flat counter automata, in relation with the satisfiability problem of three fragments of integer arithmetic. The equivalence between non-parametric flat counter automata and Presburger arithmetic has been established previously by Comon and Jurski. We simplify their proof by introducing finite state automata defined over alphabets of a special kind of graphs (zigzags). This framework allows one to express also the reachability problem for parametric automata …with one control loop as the satisfiability of a 1-parametric linear Diophantine systems. The latter problem is shown to be decidable, using a number-theoretic argument. In general, the reachability problem for parametric flat counter automata with more than one loops is shown to be undecidable, by reduction from Hilbert's Tenth Problem. Finally, we study the relation between flat counter automata, integer arithmetic, and another important class of computational devices, namely the 2-way reversal bounded counter machines. Show more

Keywords: Counter machines, Reachability problems, Diophantine systems

DOI: 10.3233/FI-2009-0044

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 275-303, 2009

Authors: Finkel, Olivier

Article Type: Research Article

Abstract: Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with usual acceptance conditions, such as the Büchi andMuller ones, in [1]. It was proved in [9] that it is undecidable whether a Büchirecognizable language of infinite pictures is E-recognizable (respectively, A-recognizable). We show here that these two decision problems are actually П^{1}_{2} -complete, hence located at the second level of the …analytical hierarchy, and "highly undecidable". We give the exact degree of numerous other undecidable problems for Büchi-recognizable languages of infinite pictures. In particular, the nonemptiness and the infiniteness problems are Σ^{1}_{1} -complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all П^{1}_{2} -complete. It is also П^{1}_{2} -complete to determine whether a given Büchi recognizable language of infinite pictures can be accepted row by row using an automaton model over ordinal words of length ω^{2} . Show more

Keywords: Languages of infinite pictures, recognizability by tiling systems, decision problems, highly undecidable problems, analytical hierarchy

DOI: 10.3233/FI-2009-0045

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 305-323, 2009

Authors: Friedl, Katalin | Santha, Miklos | Magniez, Frédéric | Sen, Pranab

Article Type: Research Article

Abstract: We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup. Our periodicity tester is efficient in Abelian groups and generalizes, in several aspects, previous …periodicity testers. This is achieved by introducing a technique refining the majority correction process widely used for proving robustness of algebraic properties. The periodicity tester in non-Abelian groups and the common coset range tester are query efficient. Show more

Keywords: Quantum Computing, Property Testing

DOI: 10.3233/FI-2009-0046

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 325-340, 2009

Authors: Istrate, Gabriel

Article Type: Research Article

Abstract: We study nondeterministic and probabilistic versions of a discrete dynamical system (due to T. Antal, P. L. Krapivsky, and S. Redner [3]) inspired by Heider's social balance theory. We investigate the convergence time of this dynamics on several classes of graphs. Our contributions include: 1. We point out the connection between the triad dynamics and a generalization of annihilating walks to hypergraphs. In particular, this connection allows us to completely characterize the recurrent states …in graphs where each edge belongs to at most two triangles. 2. We also solve the case of hypergraphs that do not contain edges consisting of one or two vertices. 3. We show that on the so-called "triadic cycle" graph, the convergence time is linear. 4. We obtain a cubic upper bound on the convergence time on 2-regular triadic simplexes G. This bound can be further improved to a quantity that depends on the Cheeger constant of G. In particular this provides some rigorous counterparts to experimental observations in [25]. We also point out an application to the analysis of the random walk algorithm on certain instances of the 3-XOR-SAT problem. Show more

Keywords: social balance, discrete dynamical systems, rapidly mixingMarkov chains, XOR-SAT

DOI: 10.3233/FI-2009-0047

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 341-356, 2009

Authors: Lippi, Sylvain

Article Type: Research Article

Abstract: We give a self-contained presentation of Hard Interaction, a rewriting system on fixed graphs. We discuss the universality of natural subclasses of hard systems and highlight the main ideas that lead to a universal system with 7 rules called Hard Combinators.

Keywords: Hard interaction nets, abstract machine, asynchronous computation, digital circuits, graph relabeling

DOI: 10.3233/FI-2009-0048

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 357-394, 2009

Authors: Lisitsa, Alexei | Potapov, Igor

Article Type: Research Article

Abstract: Querying its own history is an important mechanism in the computations, especially those interacting with people or other computations such as transaction processing, electronic data interchange. John McCarthy in his Elephant programming language proposal suggested exploiting the referring to the past as the main programming primitive. In this paper we study the computational power of such primitive. In order to do that we propose a refined formal model, History Dependent Machine (HDM), which uses querying the …history as its sole computational primitive. Our main result may be spelled in general terms as: a model with a single agent wandering around a pool of resources and having ability to check its own history for simple temporal properties has a universal computational power. Moreover, HDM can simulate any multicounter machine in real time. Then we show that the computations of HDM may be specified in the extension of propositional linear temporal logic by flexible constants, the abstraction operator and equality. We use then universality of HDM model to show that the above extension with a single flexible constant is not recursively axiomatizable. Show more

Keywords: History-dependent computations, executable temporal logic, models of computations, universality

DOI: 10.3233/FI-2009-0049

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 395-409, 2009

Authors: Stewart, Iain A.

Article Type: Research Article

Abstract: We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ_+ (1), is such that the class of problems accepted by these program schemes is exactly the class of recursively enumerable problems. The class of problems accepted by the program schemes of the class NPSQ(1) where only access to a queue, and not the …additional numeric universe, is allowed is exactly the class of recursively enumerable problems that are closed under extensions. We define an infinite hierarchy of classes of program schemes for which NPSQ(1) is the first class and the union of the classes of which is the class NPSQ.We show that the class of problems accepted by the program schemes of NPSQ is the union of the classes of problems defined by the sentences of all vectorized Lindström logics formed using operators whose corresponding problems are recursively enumerable and closed under extensions, and, as a result, has a zero-one law. Moreover, we also show that this class of problems can be realized as the class of problems defined by the sentences of a particular vectorized Lindström logic. Finally, we show how our results can be applied to yield logical characterizations of complexity classes and provide logical analogues to a number of inequalities and hypotheses from computational complexity theory involving (non-deterministic) complexity classes ranging from NP through to ELEMENTARY. Show more

Keywords: program schemes, descriptive complexity, Lindström logics, zero-one laws

DOI: 10.3233/FI-2009-0050

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 411-435, 2009