In this thesis I will be concerned with linking the observed speechsignal to the configuration of articulators.Due to the potentially rapid motion of the articulators, the speechsignal can be highly non-stationary. The typical linear analysistechniques that assume quasi-stationarity may not have sufficienttime-frequency resolution to determine the place of articulation.I argue that the traditional low and high-level primitives of speechprocessing, frequency and phonemes, are inadequate and should bereplaced by a representation with three layers: 1. short pitch periodresonances and other spatio-temporal patterns 2. articulatorconfiguration trajectories 3. syllables. The patterns indicatearticulator configuration trajectories (how the tongue, jaws, etc. aremoving), which are interpreted as syllables and words.My patterns are an alternative to frequency. I use shorttime-domain features of the sound waveform, which can be extractedfrom each vowel pitch period pattern, to identify the positions of thearticulators with high reliability. These features are importantbecause by capitalizing on detailed measurements within a single pitchperiod, the rapid articulator movements can be tracked. No linearsignal processing approach can achieve the combination of sensitivityto short term changes and measurement accuracy resulting from thesenonlinear techniques.The measurements I use are neurophysiologically plausible: theauditory system could be using similar methods.I have demonstrated this approach by constructing a robust techniquefor categorizing the English voiced stops as the consonants B, D, or Gbased on the vocalic portions of their releases. The classificationrecognizes 93.5%, 81.8% and 86.1% of the b, d and gto ae transitions with false positive rates 2.9%, 8.7% and2.6% respectively.

Durant cette thèse, nous abordons le problème de la fouille exhaustive de motifs pour un cas particulier de graphes : les grilles. Ces grilles peuvent être utilisées pour modéliser des objets ayant une structure régulière. Ces structures sont naturellement présentes dans de nombreux jeux de plateaux (les dames, les échecs ou le go par exemple) ou encore dans les modélisations d’écosystèmes utilisant des automates cellulaires. On les retrouve également à un plus bas niveau dans les images, qui sont des grilles 2D de pixels ou encore les vidéos, qui sont des grilles spatio-temporelles 2D+t de pixels. Au cours de cette thèse, nous avons proposé un nouvel algorithme de fouille de motifs fréquents dédié aux grilles spatio-temporelles, GriMA. L’usage des grilles régulières permet à notre algorithme de réduire la complexité des tests d’isomorphismes. Ces tests sont souvent utilisés par les algorithmes génériques de fouilles de graphes mais ayant une complexité importante, cela limite leur usage sur des données réelles. Deux applications ont été proposées pour évaluer notre algorithme : la classification d’images pour la fouille de grilles 2D et la prédiction d’automates cellulaires pour la fouille de grilles 2D+t. / During this thesis, we consider the exhaustive graph mining problem for a special kind of graphs : the grids. Theses grids can be used to model objects that present a regular structure. These structures are naturally present in multiple board games (checkers, chess or go for instance) or in ecosystems models using cellular automata. It is also possible to find this structure in a lower level in images, which are 2D grids of pixels, or even in videos, which are 2D+t spatio-temporal grids of pixels. In this thesis, we proposed a new algorithm to find frequent patterns dedicated to spatio-temporal grids, GriMA. Use of regular grids allow our algorithm to reduce the complexity of the isomorphisms test. These tests are often use by generic graph mining algorithm but because of their complexity, they are rarely used on real data. Two applications were proposed to evaluate our algorithm: image classification for 2D grids mining and prediction of cellular automata for 2D+t grids mining.

In contrast to established approaches that analyze networks based on their structural properties, networks can also be studied by investigating the patterns that are evolved by a discrete dynamical system built upon them, such as cellular automata (CAs). Combined with networks these tools can be used to map the relationship between the network architecture and its impact on the patterns evolved by the governing spatially discrete dynamical system. This thesis focuses on the investigation of discrete spatially explicit models (SEMs), among which are CAs, for network analysis and characterization. The relationship between network architecture and its dynamic aspects concerning pattern formation is studied. Additionally, this work aims at the development of evolutionary methods that can be employed for extracting features from such patterns and then be used as network descriptors. In order to achieve this goal, methods that integrate the network structure with the SEMs were proposed, implemented and analyzed. The proposed family of network automata is characterized by birth-survival dynamics that results in different categories of spatio-temporal patterns. Such patterns were quantitatively assessed and used to characterize different network topologies and perform classification tasks in the context of pattern recognition. Inspired by the classic Life-like CA, the proposed Life-like Network Automata (LLNA) illustrate how such tasks can be performed in real-world applications. In addition, the rock-paper-scissors (RPS) model, normally implemented on square lattices, was investigated by defining it on networks. The obtained results confirm the potential of the proposed quantitative analysis of the spatio-temporal patterns for network classification. This quantitative analysis was performed for a set of different pattern recognition tasks and for the majority of them, the classification performance improved. In addition, the reliability of LLNA as a general tool for pattern recognition applications was demonstrated in a diverse scope of classification tasks. The applicability of structural network descriptors was also highlighted in the context of shape characterization in computer vision. Through the proposed approach, the link between these network descriptors and the shape properties, such as angle and curvature, was illustrated. Moreover, when chosen adequately, the network descriptors led to a better classification performance for different shape recognition tasks. Regarding the RPS model, we demonstrated that the presence of long-range correlations in some networks directly influence the RPS dynamics. Finally, it was shown how a commuter network can be used to predict influenza outbreaks. All the proposed methods use different aspects of network analysis and contribute to the study of CAs and other SEMs on irregular tessellations, in contrast to the commonly used regular topologies. In addition, new insights were obtained concerning pattern recognition in networks through the use of spatio-temporal patterns as network descriptors. / Em contraste às abordagens clássicas que analisam redes com base em suas propriedades estruturais, as redes também podem ser estudadas investigando-se os padrões desenvolvidos por um sistema dinâmico discreto construído sobre essas redes, como os autômatos celulares (CAs). Combinadas às redes, essas ferramentas podem ser usadas para se mapear a relação entre a arquitetura da rede e seu impacto nos padrões obtidos pelo sistema dinâmico subjacente. Esta tese está focada na investigação de modelos discretos espacialmente explícitos (SEMs), entre os quais os CAs, para análise e caracterização de redes. A relação entre a arquitetura da rede e seu aspecto dinâmico em relação à formação de padrões é investigada. Além disso, este trabalho visa o desenvolvimento de métodos evolutivos que podem ser usados para extrair características de tais padrões para, então, serem usados como descritores de redes. Para atingir este objetivo, métodos que integram a estrutura da rede com os SEMs foram propostos, implementados e analisados. A família de redes-autômatos proposta é caracterizada por uma dinâmica de nascimento-sobrevivência que resulta em diferentes categorias de padrões espaço-temporais. Tais padrões foram avaliados quantitativamente e utilizados para caracterizar diferentes topologias de redes e realizar tarefas de classificação no contexto do reconhecimento de padrões. Inspirados pelo clássico Life-Like CA, a rede-autômato proposta, Life-like (LLNA), ilustra como tais tarefas podem ser realizadas em aplicações mais realistas. Além disso, o modelo de rock-paper-scissors (RPS), normalmente implementado em reticulados quadrados, foi investigado usando-se redes como tesselações. Os resultados obtidos confirmam o potencial da análise quantitativa proposta dos padrões espaço-temporais para classificação de redes. Essa análise quantitativa foi realizada para um conjunto de tarefas de reconhecimento de padrões, e, para a maioria dessas tarefas, o desempenho da classificação melhorou. Além disso, a confiabilidade do LLNA como uma ferramenta genérica para reconhecimento de padrões foi demonstrada para várias tarefas de classificação de diferentes escopos. A aplicabilidade de descritores estruturais de redes também foi destacada no contexto de caracterização de formas em visão computacional. Através da abordagem proposta, a ligação entre esses descritores de rede e as propriedades da forma, como ângulo e curvatura, foi ilustrada. Além disso, quando escolhidos adequadamente, os descritores de rede levam a um melhor desempenho de classificação para diferentes tarefas de categorização de formas. No que diz respeito ao modelo RPS, demonstramos que a presença de correlações de longo alcance nas redes afeta diretamente a dinâmica do modelo. Finalmente, foi apresentado como uma rede de transporte pode ser usada para prever surtos de gripe. Todos os métodos propostos utilizam diferentes aspectos da análise de redes e contribuem para o estudo de CAs e outras SEMs em tesselações irregulares, uma vez que estes modelos são geralmente descritos em topologias regulares. Além disso, uma nova metodologia foi proposta em relação ao reconhecimento de padrões em redes através do uso de padrões espaço-temporais como descritores da rede.