Author: Community

Automata theory based on lattice-ordered semirings

Abstract  In this paper, definitions of

K
automata,

K
regular languages,

K
regular expressions and

K
regular grammars based on lattice-ordered semirings are given. It is shown that

K
NFA is equivalent to

K
DFA under some finit…

Abstract  

In this paper, definitions of

K

automata,

K

regular languages,

K

regular expressions and

K

regular grammars based on lattice-ordered semirings are given. It is shown that

K

NFA is equivalent to

K

DFA under some finite condition, the Pump Lemma holds if

K

is finite, and

Ke

NFA is equivalent to

K

NFA. Further, it is verified that the concatenation of

K

regular languages remains a

K

regular language. Similar to classical cases and automata theory based on lattice-ordered monoids, it is also found that

K

NFA,

K

regular expressions and

K

regular grammars are equivalent to each other when

K

is a complete lattice.

  • Content Type Journal Article
  • DOI 10.1007/s00500-010-0565-3
  • Authors
    • Xian Lu, AMSS Institute of Mathematics, Academia Sinica Beijing 100190 People’s Republic of China
    • Yun Shang, AMSS Institute of Mathematics, Academia Sinica Beijing 100190 People’s Republic of China
    • Ruqian Lu, AMSS Institute of Mathematics, Academia Sinica Beijing 100190 People’s Republic of China

P systems with active membranes: trading time for space

Abstract  We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to
solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The…

Abstract  

We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to
solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved
by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules,
are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential
time and polynomial space problems that cannot be solved in polynomial time, unless P = SPACE.

  • Content Type Journal Article
  • Pages 1-16
  • DOI 10.1007/s11047-010-9189-x
  • Authors
    • Antonio E. Porreca, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336/14 20126 Milan Italy
    • Alberto Leporati, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336/14 20126 Milan Italy
    • Giancarlo Mauri, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336/14 20126 Milan Italy
    • Claudio Zandron, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336/14 20126 Milan Italy

Spatial P systems

Abstract  We present Spatial P systems, a variant of P systems which embodies the concept of space and position inside a membrane. Objects
in membranes are associated with positions. Rules specify, in the usual way, the objects which are con…

Abstract  

We present Spatial P systems, a variant of P systems which embodies the concept of space and position inside a membrane. Objects
in membranes are associated with positions. Rules specify, in the usual way, the objects which are consumed and the ones which
are produced; in addition, they can specify the positions of the produced objects. Objects belong to two different sets: the
set of ordinary objects and the set of mutually exclusive objects. Every position inside a membrane can accommodate an arbitrary number of ordinary objects, but at most one mutually
exclusive object. We prove that Spatial P systems are universal even if only non-cooperating rules are allowed. We also show
how Spatial P systems can be used to model the evolution of populations in presence of geographical separations.

  • Content Type Journal Article
  • Pages 1-14
  • DOI 10.1007/s11047-010-9187-z
  • Authors
    • Roberto Barbuti, Università di Pisa Dipartimento di Informatica Largo Pontecorvo 3 56127 Pisa Italy
    • Andrea Maggiolo-Schettini, Università di Pisa Dipartimento di Informatica Largo Pontecorvo 3 56127 Pisa Italy
    • Paolo Milazzo, Università di Pisa Dipartimento di Informatica Largo Pontecorvo 3 56127 Pisa Italy
    • Giovanni Pardini, Università di Pisa Dipartimento di Informatica Largo Pontecorvo 3 56127 Pisa Italy
    • Luca Tesei, Università di Camerino School of Science and Technology Via Madonna delle Carceri 9 62032 Camerino MC Italy

An improved multi-agent genetic algorithm for numerical optimization

Abstract  Multi-agent genetic algorithm (MAGA) is a good algorithm for global numerical optimization. It exploited the known characteristics
of some benchmark functions to achieve outstanding results. But for some novel composition functions…

Abstract  

Multi-agent genetic algorithm (MAGA) is a good algorithm for global numerical optimization. It exploited the known characteristics
of some benchmark functions to achieve outstanding results. But for some novel composition functions, the performance of the
MAGA significantly deteriorates when the relative positions of the variables at the global optimal point are shifted with
respect to the search ranges. To this question, an improved multi-agent genetic algorithm for numerical optimization (IMAGA)
is proposed. IMAGA make use of the agent evolutionary framework, and constructs heuristic search and a hybrid crossover strategy
to complete the competition and cooperation of agents, a convex mutation operator and some local search to achieve the self-learning
characteristic. Using the theorem of Markov chain, the improved multi-agent genetic algorithm is proved to be convergent.
Experiments are conducted on some benchmark functions and composition functions. The results demonstrate good performance
of the IMAGA in solving complicated composition functions compared with some existing algorithms.

  • Content Type Journal Article
  • Pages 1-20
  • DOI 10.1007/s11047-010-9192-2
  • Authors
    • Xiaoying Pan, Xi’an University of Posts and Telecommunications School of Computer Science and Technology Xi’an 710121 China
    • Licheng Jiao, Institute of Intelligent Information Processing, Xidian University Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China Xi’an 710071 China
    • Fang Liu, Xidian University School of Computer Science and Engineering Xi’an 710071 China

Comparing early and late data fusion methods for gene expression prediction

Abstract  The most basic molecular mechanism enabling a living cell to dynamically adapt to variation occurring in its intra and extracellular
environment is constituted by its ability to regulate the expression of many of its genes. At biom…

Abstract  

The most basic molecular mechanism enabling a living cell to dynamically adapt to variation occurring in its intra and extracellular
environment is constituted by its ability to regulate the expression of many of its genes. At biomolecular level, this ability
is mainly due to interactions occurring between regulatory motifs located in the core promoter regions and the transcription
factors. A crucial question investigated by recently published works is if, and at what extent, the transcription patterns
of large sets of genes can be predicted using only information encoded in the promoter regions. Even if encouraging results
were obtained in gene expression patterns prediction experiments the assumption that all the signals required for the regulation
of gene expression are contained in the gene promoter regions is an oversimplification as pointed out by recent findings demonstrating
the existence of many regulatory levels involved in the fine modulation of gene transcription levels. In this contribution,
we investigate the potential improvement in gene expression prediction performances achievable by using early and late data
integration methods in order to provide a complete overview of the capabilities of data fusion approaches in a problem that
can be annoverated among the most difficult in modern bioinformatics.

  • Content Type Journal Article
  • Pages 1-8
  • DOI 10.1007/s00500-010-0599-6
  • Authors
    • Matteo Re, Universitá degli studi di Milano Dipartimento di Scienze dell’Informazione, DSI via Comelico 39 Milan Italy

Biocircuit design through engineering bacterial logic gates

Abstract  Designing synthetic biocircuits to perform desired purposes is a scientific field that has exponentially grown over the past
decade. The advances in genome sequencing, bacteria gene regulatory networks, as well as the further knowl…

Abstract  

Designing synthetic biocircuits to perform desired purposes is a scientific field that has exponentially grown over the past
decade. The advances in genome sequencing, bacteria gene regulatory networks, as well as the further knowledge of intraspecies
bacterial communication through quorum sensing signals are the starting point for this work. Although biocircuits are mostly
developed in a single cell, here we propose a model in which every bacterium is considered to be a single logic gate and chemical
cell-to-cell connections are engineered to control circuit function. Having one genetically modified bacterial strain per
logic process would allow us to develop circuits with different behaviors by mixing the populations instead of re-programming
the whole genetic network within a single strain. Two principal advantages of this procedure are highlighted. First, the fully
connected circuits obtained where every cellgate is able to communicate with all the rest. Second, the resistance to the noise
produced by inappropriate gene expression. This last goal is achieved by modeling thresholds for input signals. Thus, if the
concentration of input does not exceed the threshold, it is ignored by the logic function of the gate.

  • Content Type Journal Article
  • Pages 1-9
  • DOI 10.1007/s11047-010-9184-2
  • Authors
    • Angel Goñi-Moreno, Universidad Politécnica de Madrid Grupo de Computación Natural, Facultad de Informática 28660 Madrid Spain
    • Miguel Redondo-Nieto, Universidad Autónoma de Madrid Depto. Biología, Facultad de Ciencias 28049 Madrid Spain
    • Fernando Arroyo, Universidad Politécnica de Madrid Depto. de Lenguajes, Proyectos y Sistemas Informáticos, Escuela Universitaria de Informática 28031 Madrid Spain
    • Juan Castellanos, Universidad Politécnica de Madrid Artificial Intelligence Department, Facultad de Informática Campus de Montegancedo, Boadilla del Monte s/n 28660 Madrid Spain

The quantification of pollutants in drinking water by use of artificial neural networks

Abstract  Drinking water attained from aquifers (ground water) is susceptible to contamination from a wide variety of sources. The importance
of ensuring that the water is of high quality is paramount. Multivariate calibration in conjunction…

Abstract  

Drinking water attained from aquifers (ground water) is susceptible to contamination from a wide variety of sources. The importance
of ensuring that the water is of high quality is paramount. Multivariate calibration in conjunction with analytical techniques
can assist in qualifying and quantifying a wide range of pollutants. These can be divided into two types: inorganic and organic.
The former typically includes heavy metals such as cadmium and lead; the latter includes a range of compounds such as pesticides
and by-products of industrial processes such as oil refining. This article presents the application of the well known nature-inspired
paradigm of artificial neural networks (ANNs) for the quantitative determination of inorganic pollutants (namely cadmium,
lead and copper) and organic pollutants (namely anthracene, phenanthrene and naphthalene) from multivariate analytical data
acquired from the samples. The success of the determination of the pollutants via ANNs is reported in terms of the overall
root mean square error of prediction (RMSEP) which is an accepted measure of the difference between the predicted concentrations
and the actual concentrations. The work represents a good example of nature-inspired methods being used to solve a genuine
environmental problem.

  • Content Type Journal Article
  • Pages 1-14
  • DOI 10.1007/s11047-010-9185-1
  • Authors
    • Michael Cauchi, Cranfield University Cranfield Health Bedfordshire MK43 0AL UK
    • Luca Bianco, Cranfield University Cranfield Health Bedfordshire MK43 0AL UK
    • Conrad Bessant, Cranfield University Cranfield Health Bedfordshire MK43 0AL UK

Advances in Computational Intelligence and Bioinformatics

Advances in Computational Intelligence and Bioinformatics
Content Type Journal ArticlePages 1-2DOI 10.1007/s00500-010-0595-xAuthors
Francesco Masulli, Università di Genova DISI, Dipartimento di Informatica e Scienze, dell’Informazione Via Dodecan…

Advances in Computational Intelligence and Bioinformatics

  • Content Type Journal Article
  • Pages 1-2
  • DOI 10.1007/s00500-010-0595-x
  • Authors
    • Francesco Masulli, Università di Genova DISI, Dipartimento di Informatica e Scienze, dell’Informazione Via Dodecaneso 35 Genoa Italy
    • Roberto Tagliaferri, Università di Salerno NeuRoNe Lab, DMI, Dipartimento di Matematica e Informatica Via Ponte don Melillo Fisciano (SA) Italy

History mechanism supported differential evolution for chess evaluation function tuning

Abstract  This paper presents a differential evolution (DE) based approach to chess evaluation function tuning. DE with opposition-based
optimization is employed and upgraded with a history mechanism to improve the evaluation of individuals …

Abstract  

This paper presents a differential evolution (DE) based approach to chess evaluation function tuning. DE with opposition-based
optimization is employed and upgraded with a history mechanism to improve the evaluation of individuals and the tuning process.
The general idea is based on individual evaluations according to played games through several generations and different environments.
We introduce a new history mechanism which uses an auxiliary population containing good individuals. This new mechanism ensures
that good individuals remain within the evolutionary process, even though they died several generations back and later can
be brought back into the evolutionary process. In such a manner the evaluation of individuals is improved and consequently
the whole tuning process.

  • Content Type Journal Article
  • Pages 1-17
  • DOI 10.1007/s00500-010-0593-z
  • Authors
    • B. Bošković, Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova ul. 17, 2000 Maribor, Slovenia
    • J. Brest, Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova ul. 17, 2000 Maribor, Slovenia
    • A. Zamuda, Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova ul. 17, 2000 Maribor, Slovenia
    • S. Greiner, Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova ul. 17, 2000 Maribor, Slovenia
    • V. Žumer, Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova ul. 17, 2000 Maribor, Slovenia

Rule acquisition and attribute reduction in real decision formal contexts

Abstract  Formal Concept Analysis of real set formal contexts is a generalization of classical formal contexts. By dividing the attributes
into condition attributes and decision attributes, the notion of real decision formal contexts is intr…

Abstract  

Formal Concept Analysis of real set formal contexts is a generalization of classical formal contexts. By dividing the attributes
into condition attributes and decision attributes, the notion of real decision formal contexts is introduced. Based on an
implication mapping, problems of rule acquisition and attribute reduction of real decision formal contexts are examined. The
extraction of “if–then” rules from the real decision formal contexts, and the approach to attribute reduction of the real
decision formal contexts are discussed. By the proposed approach, attributes which are non-essential to the maximal s rules or l rules (to be defined later in the text) can be removed. Furthermore, discernibility matrices and discernibility functions
for computing the attribute reducts of the real decision formal contexts are constructed to determine all attribute reducts
of the real set formal contexts without affecting the results of the acquired maximal s rules or l rules.

  • Content Type Journal Article
  • Pages 1-14
  • DOI 10.1007/s00500-010-0578-y
  • Authors
    • Hong-Zhi Yang, Xi’an Jiaotong University Faculty of Science Xi’an 710049 Shaan’xi People’s Republic of China
    • Leung Yee, University of Hong Kong Department of Geography and Resource Management, Center for Environmental Policy and Resource Management Hong Kong People’s Republic of China
    • Ming-Wen Shao, Shihezi University College of Information Science and Technology Shihezi 832000 Xinjiang People’s Republic of China