Computability by finite automata and pisot bases

We prove that the function of normalization in base , which maps any -representation of a real number onto its -development, obtained by a greedy algorithm, is a function computable by a finite automaton over any alphabet if and only if is a Pisot number.Christiane Frougny was supported in part by the PRC Mathématiques et Informatique of the Ministère de la Recherche et de l'Espace.     

An Experimental Comparison of the Maintainability of Object-Oriented and Structured Design Documents

Several important questions still need to be answered regarding the maintainability of object-oriented design documents. This paper focuses on the following issues: are object-oriented design documents easier to understand and modify than structured design documents? Do they need to comply with quality guidelines such as the ones provided by Coad and Yourdon? What is the impact of such quality standards on the understandability and modifiability of design documents? Answers can be based on informed opinion or empirical evidence. Since software technology investments are substantial and contradictory opinions exist regarding design strategies, performing empirical studies on these topics is a relevant research activity. This paper presents a controlled experiment performed with computer science students as subjects. Results strongly suggest that quality guidelines based on Coad and Yourdon principles have a beneficial effect on the maintainability of object-oriented design documents. However, there is no strong evidence regarding the alleged higher maintainability of object-oriented design documents over structured design documents. Furthermore, results suggest that object-oriented design documents are more sensitive to poor design practices, in part because their cognitive complexity becomes increasingly unmanageable. However, because our ability to generalise these results is limited, they should be considered as preliminary, i.e., it is very likely that they can only be generalised to programmers with little object-oriented training and programming experience. Such programmers can, however, be commonly found on maintenance projects. As well as additional research, external replications of this study are required to confirm the results and achieve confidence in these findings.     

Improved Accuracy of High-Order WENO Finite Volume Methods on Cartesian Grids

We propose a simple modification of standard weighted essentially non-oscillatory (WENO) finite volume methods for Cartesian grids, which retains the full spatial order of accuracy of the one-dimensional discretization when applied to nonlinear multidimensional systems of conservation laws. We derive formulas, which allow us to compute high-order accurate point values of the conserved quantities at grid cell interfaces. Using those point values, we can compute a high-order flux at the center of a grid cell interface. Finally, we use those point values to compute high-order accurate averaged fluxes at cell interfaces as needed by a finite volume method. The method is described in detail for the two-dimensional Euler equations of gas dynamics. An extension to the three-dimensional case as well as to other nonlinear systems of conservation laws in divergence form is straightforward. Furthermore, similar ideas can be used to improve the accuracy of WENO type methods for hyperbolic systems which are not in divergence form. Several test computations confirm the high-order accuracy for smooth nonlinear problems.     

Formal aspects of computing: LATEX style guide for authors

This guide is for authors who are preparing papers forFormal Aspects of Computing using the \(LaT_E X\) document preparation system and the FAC style file.     

Arithmetic Meyer sets and finite automata

Non-standard number representation has proved to be useful in the speed-up of some algorithms, and in the modelization of solids called quasicrystals. Using tools from automata theory we study the set of β-integers, that is, the set of real numbers which have a zero fractional part when expanded in a real base β, for a given β > 1. In particular, when β is a Pisot number — like the golden mean —, the set is a Meyer set, which implies that there exists a finite set F (which depends only on β) such that . Such a finite set F, even of minimal size, is not uniquely determined.In this paper we give a method to construct the sets F and an algorithm, whose complexity is exponential in time and space, to minimize their size. We also give a finite transducer that performs the decomposition of the elements of as a sum belonging to .     

Large, huge or gigantic? Identifying and encoding intensity relations among adjectives in WordNet

We propose a new semantic relation for gradable adjectives in WordNet, which enriches the present, vague, similar relation with information on the degree or intensity with which different adjectives express a shared attribute. Using lexical-semantic patterns, we mine the Web for evidence of the relative strength of adjectives like “large”, “huge” and “gigantic” with respect to their attribute (“size”). The pairwise orderings we derive allow us to construct scales on which the adjectives are located. To represent the intensity relation among gradable adjectives in WordNet, we combine ordered scales with the current WordNet dumbbells based on the relation between a pair of central adjectives and a group of undifferentiated semantically similar adjectives. A new intensity relation links the adjectives in the dumbbells and their concurrent representation on scales. Besides capturing the semantics of gradable adjectives in a way that is both intuitively clear as well as consistent with corpus data, the introduction of an intensity relation would potentially result in several specific benefits for NLP.     

Kinetic Facility Location

We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor larger than the optimal cost. In our scenario, each point can change its status between client and facility and moves continuously along a known trajectory in a d-dimensional Euclidean space, where d is a constant.