Date: 1999-11

Abstract:

A method for synthesizing code for the software component of a system is proposed. The specification is given as a set of concurrent processes that communicate through channels. Each process is a sequential program that may contain data-dependent control statements. The synthesized software consists of a set of tasks. A task is generated by analyzing the computation associated to the occurrence of an event at each input port connected to the environment. Our task generation and scheduling algorithm guarantees that task execution can be performed with a finite amount of inter-task buffer memory under arbitrary input streams. Petri nets are used as the underlying model to formally analyze our algorithms. This model is also used to derive several algorithms for optimizing code generation for the set of tasks yielding compact and high-performance software implementations.]]>

International Conference on Mathematical Foundations of Informatics

Presentation's date: 1999-10-27

International Conference on Mathematical Foundations of Informatics

Presentation's date: 1999-10-27

Jornadas de Enseñanza Universitaria de la Informática

p. 319-325

Presentation's date: 1999-10-25

Abstract:

Se presenta una experiencia piloto desarrollada en la asignatura de iniciación a la programación impartida en la Facultat d'Informàtica de Barcelona, durante el curso 1998/99. Dicha experiencia se centra en el uso de Java como lenguaje de programación, en sustitución de Modula-2.]]>

Bulletin of the European Association for Theoretical Computer Science

num. 69, p. 2

Date of publication: 1999-10

Date: 1999-10

Abstract:

This paper presents a novel approach to the problem of finding all subgraph isomorphisms of a (pattern) graph into another (target) graph. A relational formulation of the problem, combined with a representation of relations and graphs by Boolean functions, allows to handle the combinatorial explosion in the case of small pattern graphs and large target graphs by using Binary Decision Diagrams (BDDs), which ar= e capable to represent large relations and graphs in small data structures. Examples are presented that show how all subgraph isomorphisms (120303) of = a small graph into a large graph can be efficiently computed and represented with a small BDD (57980 nodes).]]>

Date: 1999-10

Abstract:

The incorporation of timing makes system verification computationally expensive. This paper proposes a new approach for the verification of timed circuits. Rather than calculating the exact timed state space, a conservative overestimation that fulfills the property under verification is derived. Timing analysis with absolute delays is efficiently performed at the level of event structures and transformed into a set relative timing constraints. With this approach, conventional symbolic tecniques for reachability analysis can be efficiently combined with timing analysis. Moreover, the set of timing constraints used to prove the correctness of the circuit can also be reported for backannotation purposes.]]>

Date: 1999-10

Abstract:

The diversity of application areas relying on tree-structured data results in a wide interest in algorithms which determine differences or similarities among trees. One way of measuring the similarity between trees is to find the smallest common superstructure or supertree, where common elements are typically defined in terms of a mapping or embedding. In the simplest case, a supertree will contain exact copies of each input tree, so that for each input tree, each vertex of a tree can be mapped to a vertex in the supertree such that each edge maps to the corresponding edge. More general mappings allow for the extraction of more subtle common elements captured by looser definitions of similarity. We consider supertrees under the general mapping of minor containment. Minor containment generalizes both subgraph isomorphism and topological embedding; as a consequence of this generality, however, it is NP-complete to determine whether or not G is a minor of H, even for general trees. By focusing on trees of bounded degree, we obtain an O(n^3) algorithm which determines the smallest tree T such that both of the input trees are minors of T, even when the trees are assumed to be unrooted and unordered.]]>

Date: 1999-10

Abstract:

In general, graph search can be described in terms of a sequence of searchers' moves on a graph, able to capture a fugitive resorting on its vertices/edges. Several variations of graph search have been introduced, differing on the abilities of the fugitive as well as of the search. In this paper, we examine the case where the fugitive is inert, i.e., it moves only whenever the search is about to capture it. Mainly, there are two variants for "clearing'' an edge during a search: when a sliding of a searcher occurs along the edge or when both its endpoints are simultaneously occupied by searchers. These variants define the inert edge search and the inert node search respectively. A third search variant, the inert mixed search, is defined when both ways of clearing an edge are possible. As we show, inert search and inert mixed search are equivalent (surprisingly, this is not the case if we discard the inertness property). Moreover, we prove that, in any case, by restricting the searches to only those that always reduce further the fugitive's possible resorts, does not give any advantage to the fugitive (this monotonicity property is usually expressed as: ``recontamination does not help''). So far, the only monotonicity result on inert search concerns inert node search and our results yield a much simpler proof of that result as well. Furthermore, we define a new graph-theoretic parameter, the proper-treewidth, in analogy to the parameter proper-pathwidth, and prove it equivalent to the inert mixed search game. Last, we prove that proper-treewidth, in turn, is equivalent to a known graph theoretic parameter related to treewidth.

In general, graph search can be described in terms of a sequence of searchers' moves on a graph, able to capture a fugitive resorting on its vertices/edges. Several variations of graph search have been introduced, differing on the abilities of the fugitive as well as of the search. In this paper, we examine the case where the fugitive is inert, i.e., it moves only whenever the search is about to capture it. Mainly, there are two variants for]]>

Date of publication: 1999-10

Bulletin of the European Association for Theoretical Computer Science

num. 69, p. 1-2

Date of publication: 1999-10

Bulletin of the European Association for Theoretical Computer Science

num. 69, p. 98-109

Date of publication: 1999-10

Date of publication: 1999-09-30

14th International Workshop on Algebraic Development Techniques (WADT`99)

Presentation's date: 1999-09-17

Lecture notes in computer science

Vol. 1665, p. 291-302

Date of publication: 1999-09

IEEE transactions on computer-aided design of integrated circuits and systems

Vol. 18, num. 9, p. 1221-1236

DOI: 10.1109/43.784116

Date of publication: 1999-09

Abstract:

This paper presents a new technique for decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The proposed method iteratively performs Boolean decomposition of each such gate F into a two-input combinational or sequential gate G available in the library and two gates H/sub 1/ and H/sub 2/ simpler than F, while preserving the original behavior and speed-independence of the circuit. To extract functions for H/sub 1/ and H/sub 2/ the method uses Boolean relations as opposed to the less powerful algebraic factorization approach used in previous methods. After logic decomposition, the overall library matching and optimization is carried out. Logic resynthesis, performed after speed-independent signal insertion for H/sub 1/ and H/sub 2/, allows for sharing of decomposed logic. Overall, this method is more general than the existing techniques based on restricted decomposition architectures, and thereby leads to better results in technology mapping.]]>

Lecture notes in computer science

Vol. 1709, p. 1778-1796

Date of publication: 1999-09

Lecture notes in computer science

Vol. 1627, p. 103-112

Date of publication: 1999-07

Date: 1999-07

Abstract:

This paper presents a simple method to build tree data structures which achieve just O(log N) visited nodes and O(D) compared digits (bits or bytes) per search or update, where N is the number of keys and D is the length of the keys, irrespectively of the order of the updates and of the digital representation of the keys. The additional space required by the method is asymptotically dismissable compared to the space of keys and pointers, and is easily updated on line. The method applies to fixed-length base-2 keys and to variable-length string keys as well, and permits to save space for common prefixes. The same ideas can be applied to the sorting problem, achieving algorithms with the best properties of quicksort/mergesort and radixsort together.]]>

Date: 1999-07

Abstract:

System verification in the broadest sense deals with those semantic properties that can be decided or deduced by analyzing a syntactical description of the system. Hence, one may consider the notions of redundancy and subsumption in this context as they are known from the area of rule-based systems. A rule is redundant if it can be removed without affecting the semantics of the system; it is subsumed by another rule if each application of the former one can be replaced by an application of the latter one with the same effect. In this paper, redundancy and subsumption are carried over from rule-based systems to high-level replacement systems, which in turn generalize graph and hypergraph grammars. The main results presented in this paper are a characterization of subsumption and a sufficient condition for redundancy, which involves composite productions.]]>

Date: 1999-07

Abstract:

Grammatica is a prototype implementation of algebraic graph transformation based on relation algebra. It has been implemented using Mathematica on top of the Combinatorica package, and runs therefore on most platforms. It consists of Mathematica routines for representing, manipulating, displaying and transforming graphs, as well as routines implementing some relation algebra-theoretic operations on graphs. It supports both interactive and automatic application of double-pushout graph productions, being therefore both a teaching aid and a research tool for algebraic graph transformation.]]>

Date: 1999-07

Abstract:

A west ordering is a well-founded (strict partial) ordering on terms that satisfies the subterm property. In [Bofill, Godoy, Nieuwenhuis, Rubio, (BGNR-LICS99)] the completeness of an ordered paramodulation inference system w.r.t. west orderings was proved, thus dropping for the first time the monotonicity requirements on the ordering. However, the inference system still required the eager selection of negative equations. Here we improve upon [BGNR-LICS99] in two directions. On the one hand, we show that the results are compatible with constraint inheritance and the so-called basic strategy [(Bachmair, Ganzinger, Lynch, Snyder (1995IC)), (Nieuwenhuis, Rubio (1995JSC))], thus further restricting the search space. On the other hand, we introduce an inference system where also the positive equations of non-unit clauses can be selected, provided that they are maximal.]]>

Bulletin of the European Association for Theoretical Computer Science

num. 68, p. 1-2

Date of publication: 1999-06

Bulletin of the European Association for Theoretical Computer Science

num. 68, p. 18-19

Date of publication: 1999-06

International Symposium on Advanced Research in Asynchronous Circuits and Systems

Presentation's date: 1999-04-19

Date: 1999-04

Abstract:

This work deals with convergence theorems and bounds on the cost of several layout measures for lattice graphs, random lattice graphs and sparse random geometric graphs. For full square lattices, we give optimal layouts for the problems still open. Our convergence theorems can be viewed as an analogue of the Beardwood, Halton and Hammersley theorem for the Euclidian TSP on random points in the $d$-dimensional cube. As the considered layout measures are non-subadditive, we use percolation theory to obtain our results on random lattices and random geometric graphs. In particular, we deal with the subcritical regimes on these class of graphs.]]>

Date: 1999-04

Abstract:

In random geometric graphs, vertices are randomly distributed on [0,1]^2 and pairs of vertices are connected by edges whenever they are sufficiently close together. Layout problems seek a linear ordering of the vertices of a graph such that a certain measure is minimized. In this paper, we study several layout problems on random geometric graphs: Bandwidth, Minimum Linear Arrangement, Minimum Cut, Minimum Sum Cut, Vertex Separation and Bisection. We first prove that some of these problems remain \NP-complete even for geometric graphs. Afterwards, we compute lower bounds that hold with high probability on random geometric graphs. Finally, we characterize the probabilistic behavior of the lexicographic ordering for our layout problems on the class of random geometric graphs.]]>

Date: 1999-04

Abstract:

This paper studies the computational complexity of the Proper Interval Colored Graph problem (PICG), when the input graph is a colored tree. We show that the problem is hard for the class of caterpillar trees. To prove our result we make use of a close relationship between intervalizing problems and graph layout problems. We define a graph layout problem the Proper Colored Layout Problem (PCLP). Although PCLP is not equivalent to PICG, by transforming the input graph we will stablish a close relationship between both problems. The main result is that the PICG is NP-complete for colored caterpillars of hair length 2 and in P for caterpillars of hair length 1 or 0.]]>

Date: 1999-04

Abstract:

In BSP a superstep comprises a collection of concurrently executed processes with initial and terminal synchronisations. Data transfer between processes is realised through asynchronous communications. BSP programs can be organised either as explicit compositions of supersteps or as parallel compositions of threads (processes) which include synchronisation alignment operations. In this paper axiomatic semantics for the two approaches are proposed: in both cases the semantics are based on a new form of multiple substitution - predicate substitution which generalises previous definitions of substitution. Predicate substitution together with global synchronisation provide a means of linking state based and process semantics of BSP.]]>

Date: 1999-04

Abstract:

The fringe analysis studies the distribution of bottom subtrees or fringe of trees under the assumption of random selection of keys, yielding an average case analysis of the fringe of trees. We are interested in the fringe analysis of the synchronized parallel insertion algorithms of Paul, Vishkin, and Wagener~(PVW) on 2-3 trees. This algorithm inserts k keys with k processors into a tree of size n with time O(log n+log k). As the direct analysis of this algorithm is very difficult we tackle this problem by introducing a new family of algorithms, denoted MacroSplit algorithms, and our main theorem proves that two algorithms of this family, denoted MaxMacroSplit and MinMacroSplit, upper and lower bounds the fringe of the PVW algorithm. Published papers deal with the fringe analysis of sequential algorithms and it was an open problem for parallel algorithms on search trees. We extend the fringe analysis to parallel algorithms and we get a rich mathematical structure giving new interpretations even in the sequential case. We prove that the random selection of keys generates a binomial distribution of them between leaves, that the synchronized insertions of keys can be modeled by a Markov chain, and that the coefficients of the transition matrix of the Markov Chain are related with the expected local behavior of our algorithm. Finally, we show that the coefficients of the power expansion of this matrix over (n+1)^{-1} are the binomial transform of the expected local behavior of the algorithm.]]>

Date: 1999-04

Abstract:

We present a highly tuned mergesort algorithm that improves the cost bounds when used to sort linked lists of elements. We provide empirical comparisons of our algorithm with other mergesort algorithms. The paper also illustrates the sort of techniques that allow to speed a divide-and-conquer algorithm.]]>

Date: 1999-04

Abstract:

A new experience in programming education is explained. It has happened at the Facultat d'Informàtica de Barcelona (FIB) into a course named Iniciació a la Programació (Beginning to Programming), also nicknamed as IniPro. The main goal was to achieve a higher motivation in the students. We've used for the first time Java as programming language. This fact has allowed teaching what students "wanted to learn" (windows, menus, mouse) and what students "should learn" (basic algorithms and program design methods). Although the work developed by the student in the laboratory sessions is highly valued, students were able to make a part of their work at home by means of Internet connection, too.

A new experience in programming education is explained. It has happened at the Facultat d'Informàtica de Barcelona (FIB) into a course named Iniciació a la Programació (Beginning to Programming), also nicknamed as IniPro. The main goal was to achieve a higher motivation in the students. We've used for the first time Java as programming language. This fact has allowed teaching what students]]>

ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Difital Systems

Presentation's date: 1999-03-08

Theoretical computer science

Vol. 216, num. 1-2, p. 311-362

DOI: 10.1016/S0304-3975(97)00282-X

Date of publication: 1999-03-06

Abstract:

The single-pushout approach to graph transformation is extended to the algebraic transformation of partial many-sorted unary algebras. Such a generalization has been motivated by the need to model the transformation of structures which are richer and more complex than graphs and hypergraphs. The main result presented in this article is an algebraic characterization of the single-pushout transformation in the categories of all conformisms, all closed quomorphisms, and all closed-domain closed quomorphisms of unary partial algebras over a given signature, together with a corresponding operational characterization that may serve as a basis for implementation. Moreover, all three categories are shown to satisfy all of the HLR (high-level replacement) conditions for parallelism, taking as occurrences the total morphisms in each category. Another important result presented in this article is the definition of HLR conditions for amalgamation, which are also satisfied by the categories of partial homomorphisms considered here, taking again the corresponding total morphisms as occurrences.]]>

Mathematical structures in computer science

Vol. 9, num. ., p. 21-62

Date of publication: 1999-03

Les Tecnologies de la Informació i les Comunicacions en l'Educació a la UPC

Presentation's date: 1999-02-10

Proceedings of the IEEE

Vol. 87, num. 2, p. 347-362

DOI: 10.1109/5.740027

Date of publication: 1999-02

Abstract:

Logic decomposition is a well-known problem in logic synthesis, but it poses new challenges when targeted to speed-independent circuits. The decomposition of a gate into smaller gates must preserve not only the functional correctness of a circuit but also speed independence, i.e., hazard freedom under unbounded gate delays. This paper presents a new method for logic decomposition of speed-independent circuits that solves the problem in two major steps: (1) logic decomposition of complex gates and (2) insertion of new signals that preserve hazard freedom. The method is shown to be more general than previous approaches and its effectiveness is evaluated by experiments on a set of benchmarks.]]>

Date of publication: 1999-02

Bulletin of the European Association for Theoretical Computer Science

num. 67, p. 1-2

Date of publication: 1999-02

Journal of logic programming

Vol. 40, num. 1, p. 89-124

Date of publication: 1999-02

International Conference on Mathematical Foundations of Informatics

p. 2-3

Annual ACM/IEEE Symposium on Logic in Computer Science

p. 225-233

APPIA-GULP-PRODE`97 Joint Conference on Declarative Programming

p. 43-58

International Conference on Mathematical Foundations of Informatics

p. 38-39

International Conference on Mathematical Foundations of Informatics

p. 16-19