Catálogo de publicaciones - libros

We use stochastic deterministic finite automata to model musical styles: a same automaton can be used to classify new melodies but also to generate them. Through grammatical inference these automata are learned and new pieces of music can be parsed. We show that this works by proposing promising classification results.

Soliton circuits are among the most promising alternatives for molecular electronic devices based on the design of molecular level conventional digital circuits. In order to capture the logical and computational aspects of these circuits, a mathematical model called soliton automaton was introduced by Dassow and Jürgensen in 1990.

Computing short regular expressions equivalent to a given finite automaton is a hard task. We present a class of acyclic automata for which it is easy-to-find a regular expression that has linear size. We call those automata UDR. A UDR automaton is characterized by properties of its underlying digraph. We give a characterisation theorem and an efficient algorithm to determine if an acyclic automaton is UDR, that can be adapted to compute an equivalent short regular expression.

We study a formal model of imperative sequential programs and focus on the equivalence problem for some class of programs with mode switching whose runs can be divided into two stages. In the first stage a program selects an appropriate mode of computation. Several modes may be tried (switched) in turn before making the ultimate choice. Every time when the next mode is put to a test, the program brings data to some predefined state. In the second stage of the run, once a definite mode is fixed, the final result of computation is produced. We develop a new technique for simulating the behavior of such programs by means of finite automata and demonstrate that the equivalence problem for programs with mode switching is decidable within a polynomial space. By revealing a close relationships between the equivalence problem for this class of programs and the intersection emptiness problem for deterministic finite automata we show that the the former is -complete.

AB-categorial grammars (CGs in the following) is a lexicalized formalism having the expressive power of -free context-free languages [1]. It has a long common history with natural language [2]. Here, we first relate unidirectional CGs to a special case of recursive transition networks [3]. We then illustrate how the structures produced by a CG can be generated by a .

We show that an infinite isometry on {0,1}, computable by an infinite transducer , can be represented finitarily, provided the isometry [,] := ∘ ∘ ∘ , the shift commutator of , is finite, has a finite transducer . We can describe all states of as words over and, using the nextstate and output functions of , obtain linear time algorithms for (in the length of the word in describing the state in ). The task of determining state equivalence within the first input symbols or =2-1 states is in the number of states, if the shift commutator is finite.