Catálogo de publicaciones - libros

There are several nonequivalent definitions of quantum finite automata. Nearly all of them recognize only regular languages but not all regular languages. On the other hand, for all these definitions there is a result showing that there is a language such that the size of the quantum automaton recognizing is essentially smaller than the size of the minimal deterministic automaton recognizing .

For most of the definitions of quantum finite automata the problem to describe the class of the languages recognizable by the quantum automata is still open. The partial results are surveyed in this paper. Moreover, for the most popular definition of the QFA, the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.

The end of the paper is devoted to unpublished results of the description of the class of the recognizable languages in terms of the second order predicate logics. This research is influenced by the results of Büchi [1,2], Elgot [3], Trakhtenbrot [4] (description of regular languages in terms of MSO), R.Fagin [5,6] (description of NP in terms of ESO), von Neumann [7] (quantum logics), Barenco, Bennett et al. [8](universal quantum gates).

This survey paper reviews the means that allow to go from one representation of the languages to the other and how, and to what extend, one can keep them small. Some emphasis is put on the comparison between the expressions that can be computed from a given automaton and on the construction of the derived term automaton of an expression.

There has been several attempts over the years to solve the bisimulation minimization problem for finite automata. One of the most famous algorithms is the one suggested by Paige and Tarjan. The algorithm has a complexity of ( log ) where is the number of edges and is the number of states in the automaton. A bottleneck in the application of the algorithm is often the number of labels which may appear on the edges of the automaton. In this paper we adapt the Paige-Tarjan algorithm to the case where the labels are symbolically represented using Binary Decision Diagrams (BDDs). We show that our algorithm has an overall complexity of where ℓ is the size of the alphabet. This means that our algorithm will have the same worst case behavior as other algorithms. However, as shown by our prototype implementation, we get a vast improvement in performance due to the compact representation provided by the BDDs.

The aim of this paper is to investigate sequential models to describe two-dimensional languages. The intent is to add more capabilities to 4NFA in order to encompass a wider class of languages. We show that any (tiling) recognizable language can be simulated by a 4NFA with an extra queue whose size is bounded by the minimum of the two dimensions of a picture; and that 2NFA (i.e. automata moving only in two directions) with an analogous queue are sufficient when the alphabet is unary. A special class of recognizable languages can be simulated also by 4-way pushdown automata with a stack of size bounded by the sum of the two dimensions of the picture. Such a class is also characterized by a recursive definition involving the operations of union, intersection and a new diagonal overlapping operation applied to languages recognized by 2NFA.

This paper investigates the compositional properties of reusable software components defined with explicit dependencies and behavioural contracts expressing rely-guarantee specifications in the form of communication traces. In this setting, connection of components through their matching ports is indeed compositional and yields a new component or that respects its constituents’ contracts. Thus the behaviour of the composite is computed from the behaviours of its constituents and is known to conform to the contracts without any new proof.

Strong retiming equivalence is the join of two basic equivalence relations of synchronous schemes: strong equivalence and retiming equivalence, which play an important role in the optimization of synchronous systems. Each of these equivalences is characterized separately in an algebraic/category theoretic framework, and the characterization is carried over to the join of them. Tree-reducible schemes are introduced to facilitate the proof that strong retiming equivalence is decidable.

A prefix-free language is a prime if it cannot be decomposed into a concatenation of two prefix-free languages. We show that we can check in polynomial time if a language generated by a simple context-free grammar is a prime. Our algorithm computes a canonical representation of a simple language, converting its arbitrary simple grammar into Prime Normal Form (PNF); a simple grammar is in PNF if all its nonterminals define primes. We also improve the complexity of testing the equivalence of simple grammars. The best previously known algorithm for this problem worked in () time. We improve it to ( log) and ( polylog ) deterministic time, and ( polylog ) randomized time, where is the total size of the grammars involved, and is the length of a shortest string derivable from a nonterminal, maximized over all nonterminals. Our improvement is based on a version of Caucal’s algorithm from [1].

We present a fast incremental algorithm for constructing minimal DFCA for a given language. Since it was shown that the DFCA for a language can have less states than the DFA for , this technique seems to be the best choice for incrementally building the automaton for a large language, especially when the number of states in the DFCA is significantly less than the number of states in the corresponding minimal DFA. We have implemented the proposed algorithm and have tested it against the best known DFCA minimization technique.

The class of unbounded unions of regular pattern languages with bounded constant segments is identifiable from positive data in the limit [1]. Otherwise, no efficient algorithm that performs the inference of this class of languages is known. We propose a solution to this problem using the existing connexion between the positive variety of languages of dot depth 1/2, [2] and the class of unbounded union of pattern languages .

This paper presents some features of the platform. We describe some original algorithms on weighted automata and transducers (computation of the quotient, conversion of a regular expression into a weighted automaton, and composition). We explain how complex declarations due to the generic programming are masked from the user and finally we present a proposal for an XML format that allows implicit descriptions for simple types of automata.