Search results for "Automata"

Cellular automata and urban development simulation : a transition rules creation process based on statistical analysis

2015

National audience; Nowadays land use evolution study has become a major stake in urban planning. The main focus is to understand the way in which land use evolves across time and to understand processes that take place. This understanding would allow to plan urban developments based on a knowledge as complete as possible covering as many fields as possible (i.e. urban planning, politics, sociology, etc.). Simulation tools can be used to merge and display different points of view and stakes from different stakeholders (Parrott & Meyer, 2012).

Generating Multi State Cellular Automata by using Chua’s ”Universal Neuron”

2007

Debates with Small Transparent Quantum Verifiers

2014

We study a model where two opposing provers debate over the membership status of a given string in a language, trying to convince a weak verifier whose coins are visible to all. We show that the incorporation of just two qubits to an otherwise classical constant-space verifier raises the class of debatable languages from at most NP to the collection of all Turing-decidable languages (recursive languages). When the verifier is further constrained to make the correct decision with probability 1, the corresponding class goes up from the regular languages up to at least E.

Pseudocomplements in sum-ordered partial semirings

2007

We study a particular way of introducing pseudocomplementation in ordered semigroups with zero, and characterise the class of those pseudocomplemented semigroups, termed g-semigroups here, that admit a Glivenko type theorem (the pseudocomplements form a Boolean algebra). Some further results are obtained for g-semirings – those sum-ordered partially additive semirings whose multiplicative part is a g-semigroup. In particular, we introduce the notion of a partial Stone semiring and show that several well-known elementary characteristics of Stone algebras have analogues for such semirings.

On a class of languages with holonomic generating functions

2017

We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM

On Horn spectra

1991

Abstract A Horn spectrum is a spectrum of a Horn sentence. We show that to solve Asser's problem, and consequently the EXPTIME = ? NEXPTIME question it suffices to consider the class of Horn spectra. We also pose the problem whether or not the generator of every Horn spectrum is a spectrum. We prove that from a negative solution of the generator problem, a negative answer for the EXPTIME = ? NEXPTIME question follows. Some other relations between the generator problem and Asser's problem are given. Finally, the relativized version of the generator problem is formulated and it is shown that it has an affirmative solution for some oracles, and a negative solution for some others.

Modeling the role of climate change on small-scale vegetation patterns in a Mediterranean basin using a Cellular Automata model

2013

Predicting vegetation response in regions of ecotone transition under a changing climate is a among grand challenges in ecohydrology. In a small basin (1.3 sq km) in Sicily, Italy, where north-facing slopes are characterized by Quercus (tree), and south-facing slopes by Opuntia ficus-indaca (evergreen perennial species drought tolerant) and grasses we use an ecohydrological Cellular-Automaton model (CATGraSS) of vegetation coexistence driven by rainfall and solar radiation with downscaled future climate to examine the role of climate change on vegetation patterns. In the model, each cell can hold a single plant type or can be bare soil. Plant competition is modeled explicitly by keeping tra…

Balance Properties and Distribution of Squares in Circular Words

2008

We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalised to non periodic infinite words as well.

"Indexing structures for approximate string matching

2003

In this paper we give the first, to our knowledge, structures and corresponding algorithms for approximate indexing, by considering the Hamming distance, having the following properties. i) Their size is linear times a polylog of the size of the text on average. ii) For each pattern x, the time spent by our algorithms for finding the list occ(x) of all occurrences of a pattern x in the text, up to a certain distance, is proportional on average to |x| + |occ(x)|, under an additional but realistic hypothesis.

Hamming, Permutations and Automata

2007

Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than superexponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…