Author name cluster

Marco Carpentieri

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2006 Journal Article

A genetic system based on simulated crossover of sequences of two-bit genes

Marco Carpentieri

We introduce a genetic model based on simulated crossover of fixed sequences of two-bit genes. Results are (1) a lower bound on population size is exhibited such that a transition takes the stochastic finite population genetic system near the next state of the deterministic infinite population genetic system (provided both begin in the same state); (2) states and dynamics of the deterministic infinite population genetic system are derived for arbitrary (finite) fitness functions (expressed in terms of multivariate polynomials); (3) in the case of quadratic fitness defined by weight matrices with m nonnull entries it is shown that each state transition can be implemented in time O ( m + l ), where l is the chromosome length; (4) the genetic algorithm (implementing the proposed infinite population system) is experimentally compared with the infinite population genetic algorithm with bit-based simulated crossover for the max-cut problem; the results show that the extension to sequences of genes with four alleles is useful to improve performances.

Details DOI

TCS Journal 2003 Journal Article

On the simulation of quantum turing machines

Marco Carpentieri

In this article we shall review several basic definitions and results regarding quantum computation. In particular, after defining Quantum Turing Machines and networks the paper contains an exposition on continued fractions and on errors in quantum networks. The topic of simulation of Quantum Turing Machines by means of obvious computation is introduced. We give a full discussion of the simulation of multitape Quantum Turing Machines in a slight generalization of the class introduced by Bernstein and Vazirani. As main result we show that the Fisher-Pippenger technique can be used to give an O(tlogt) simulation of a multi-tape Quantum Turing Machine by another belonging to the extended Bernstein and Vazirani class. This result, even if regarding a slightly restricted class of Quantum Turing Machines improves the simulation results currently known in the literature.

Details DOI

TCS Journal 2001 Journal Article

Analogies and differences between quantum and stochastic automata

Alberto Bertoni
Marco Carpentieri

We analyze some features of the behaviour of quantum automata, providing analogies and differences with the corresponding stochastic models. In particular, we prove: • there is a quantum automaton where the change of state depends on unitary transformations defined by matrices with nonnull amplitudes that accepts a non regular language with cut point zero and inverse error polynomially bounded, • stochastic automata with matrices having nonnull elements and with polynomial bounds on the inverse error recognize only regular languages, • the class of stochastic languages contains the class of quantum languages, • quantum languages are empty or contain an infinite number of words, • the class of quantum languages is not closed under complementation.

Details DOI

I&C Journal 2001 Journal Article

Regular Languages Accepted by Quantum Automata

Alberto Bertoni
Marco Carpentieri

In this paper we analyze some features of the behaviour of quantum automata. In particular we prove that the class of languages recognized by quantum automata with isolated cut point is the class of reversible regular languages. As a more general result, we give a bound on the inverse error that implies the regularity of the language accepted by a quantum automaton.

Details DOI