Search results for "AUTOMATA"
showing 10 items of 453 documents
Asymptotic bit frequency in Fibonacci words
2021
It is known that binary words containing no $k$ consecutive 1s are enumerated by $k$-step Fibonacci numbers. In this note we discuss the expected value of a random bit in a random word of length $n$ having this property.
Coupling Cellular Automata and Markov Chains to Design prospective Scenarios of Urbanization. An application to Strasbourg Cross-border Area
2016
International audience
Land use simulation: statistical analysis approaches to calibrate cellular automata
2015
International audience
Constraint Cellular Automata for Urban Development simulation. An Application to Strasbourg Cross-border Area
2015
International audience
SYSTEM DYNAMICS VERSUS CELLULAR AUTOMATA IN MODELLING PANIC SITUATIONS
2008
International audience; In this paper we face system dynamics modelling and cellular automata to model panic processes. We compare both models using phase plans. The results of simulation confirm our hypotheses: First, a collective behaviour is not the arithmetical sum of the individual behaviours. Secondly the crowd causes the emergence of collective panic from individual panic. Both types of methodology produce the emergence of panic and identical curves for different values of initial conditions and parameters. But the effects of thresholds vary according to these values.
On-line construction of a small automaton for a finite set of words
2009
In this paper we describe a ``light'' algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on the suffixes of a text, showing how this automaton is small. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton.
On the suffix automaton with mismatches
2007
International audience; In this paper we focus on the construction of the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of S_k in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.
A trie-based approach for compacting automata
2004
International audience; We describe a new technique for reducing the number of nodes and symbols in automata based on tries. The technique stems from some results on anti-dictionaries for data compression and does not need to retain the input string, differently from other methods based on compact automata. The net effect is that of obtaining a lighter automaton than the directed acyclic word graph (DAWG) of Blumer et al., as it uses less nodes, still with arcs labeled by single characters.
Machine learning for land use change analysis and modelling.
2019
Urban development can take different forms or features, depending on its geographical location and its socioeconomic, political and cultural context. Nevertheless, the overall action relies on one fundamental principle: building construction in order to give people housing. Therefore, the main objective of this research is to determine whether an underlying universal aspect of the urban development process can be distinguished from a specific one, being the reflect of local specificities. Specifically, this research analyzes the land use change on the French-German cross-border area. Indeed, the border context enhances the difference within this territory. Nonetheless, the internal European…
Pattern languages with and without erasing
1994
The paper deals with the problems related to finding a pattern common to all words in a given set. We restrict our attention to patterns expressible by the use of variables ranging over words. Two essentially different cases result, depending on whether or not the empty word belongs to the range. We investigate equivalence and inclusion problems, patterns descriptive for a set, as well as some complexity issues. The inclusion problem between two pattern languages turns out to be of fundamental theoretical importance because many problems in the classical combinatorics of words can be reduced to it.