Episciences.org
Not a member yet
6707 research outputs found
Sort by
Differentials and distances in probabilistic coherence spaces
No full textIn probabilistic coherence spaces, a denotational model of probabilisticfunctional languages, morphisms are analytic and therefore smooth. We exploretwo related applications of the corresponding derivatives. First we show howderivatives allow to compute the expectation of execution time in the weak headreduction of probabilistic PCF (pPCF). Next we apply a general notion of"local" differential of morphisms to the proof of a Lipschitz property of thesemorphisms allowing in turn to relate the observational distance on pPCF termsto a distance the model is naturally equipped with. This suggests thatextending probabilistic programming languages with derivatives, in the spiritof the differential lambda-calculus, could be quite meaningful.Comment: extended version of arXiv:1902.04836 . Improved redaction of the proof of the main result of Section 2 (expectation of computation time
Addressing Machines as models of lambda-calculus
No full textTuring machines and register machines have been used for decades intheoretical computer science as abstract models of computation. Also the-calculus has played a central role in this domain as it allows tofocus on the notion of functional computation, based on the substitutionmechanism, while abstracting away from implementation details. The presentarticle starts from the observation that the equivalence between theseformalisms is based on the Church-Turing Thesis rather than an actual encodingof -terms into Turing (or register) machines. The reason is that thesemachines are not well-suited for modelling -calculus programs. We study a class of abstract machines that we call "addressing machine" sincethey are only able to manipulate memory addresses of other machines. Theoperations performed by these machines are very elementary: load an address ina register, apply a machine to another one via their addresses, and call theaddress of another machine. We endow addressing machines with an operationalsemantics based on leftmost reduction and study their behaviour. The set ofaddresses of these machines can be easily turned into a combinatory algebra. Inorder to obtain a model of the full untyped -calculus, we need tointroduce a rule that bares similarities with the -rule and the rule from combinatory logic
Automatic sequences: from rational bases to trees
No full textThe th term of an automatic sequence is the output of a deterministicfinite automaton fed with the representation of in a suitable numerationsystem. In this paper, instead of considering automatic sequences built on anumeration system with a regular numeration language, we consider those builton languages associated with trees having periodic labeled signatures and, inparticular, rational base numeration systems. We obtain two maincharacterizations of these sequences. The first one is concerned with -blocksubstitutions where morphisms are applied periodically. In particular, weprovide examples of such sequences that are not morphic. The secondcharacterization involves the factors, or subtrees of finite height, of thetree associated with the numeration system and decorated by the terms of thesequence.Comment: 26 pages, 16 figures; final version accepted for publication in Discrete Mathematics & Theoretical Computer Scienc
Characteristic Logics for Behavioural Hemimetrics via Fuzzy Lax Extensions
No full textIn systems involving quantitative data, such as probabilistic, fuzzy, ormetric systems, behavioural distances provide a more fine-grained comparison ofstates than two-valued notions of behavioural equivalence or behaviourinclusion. Like in the two-valued case, the wide variation found in systemtypes creates a need for generic methods that apply to many system types atonce. Approaches of this kind are emerging within the paradigm of universalcoalgebra, based either on lifting pseudometrics along set functors or onlifting general real-valued (fuzzy) relations along functors by means of fuzzylax extensions. An immediate benefit of the latter is that they allow boundingbehavioural distance by means of fuzzy (bi-)simulations that need notthemselves be hemi- or pseudometrics; this is analogous to classicalsimulations and bisimulations, which need not be preorders or equivalencerelations, respectively. The known generic pseudometric liftings, specificallythe generic Kantorovich and Wasserstein liftings, both can be extended to yieldfuzzy lax extensions, using the fact that both are effectively given by achoice of quantitative modalities. Our central result then shows that in factall fuzzy lax extensions are Kantorovich extensions for a suitable set ofquantitative modalities, the so-called Moss modalities. For nonexpansive fuzzylax extensions, this allows for the extraction of quantitative modal logicsthat characterize behavioural distance, i.e. satisfy a quantitative version ofthe Hennessy-Milner theorem; equivalently, we obtain expressiveness of aquantitative version of Moss' coalgebraic logic. All our results explicitlyhold also for asymmetric distances (hemimetrics), i.e. notions of quantitativesimulation
Pomiędzy zmianą a kontynuacją: polifoniczne igraszki i kreatywność frazeologiczna w języku młodzieży
No full textÉpisciences - SlovoThe present paper deals with linguistic novelties in contemporary Polish. Indeed, every day communication brings out a large variety of new forms and formulæ. Nevertheless, rather than changes, they mostly remain innovations. Having considered, in the first part, main tendencies in contemporary Polish, the second part discusses findings of a compared analysis of 553 nominal phrases (NP) extracted from two sources: an online dictionary of urban slang (Miejski) and short humoristic stories published between 1935 et 1937. The results suggest similarities in speakers’ attitudes, in particular as far as poliphonic phraseological creativity is concerned.L’article propose une réflexion sur des phraséologismes nominaux extraits de Miejski, dictionnaire du parler de jeunes Polonais. La première partie expose les principales tendances et nouveautés repérées dans le polonais de la période post-transitionnelle. La seconde partie est consacrée à une analyse comparée de 553 unités phraséologiques extraites de Miejski et de chroniques humoristiques de Stefan Wiechecki publiées entre 1935 et 1937. Cette comparaison fait apparaître des continuités de comportements langagiers, notamment pour ce qui est du recours aux procédés polyphoniques chez des locuteurs de deux époques différentes.Niniejszy artykuł poświęcony jest tematyce zmian we współczesnej polszczyźnie. Pierwsza część przedstawia najważniejsze tendencje opisane w badaniach zrealizowanych od końca lat dziewięćdziesiątych do dnia dzisiejszego. Część druga prezentuje wyniki analizy porównawczej 553 fraz rzeczownikowych pochodzących z dostępnego w sieci Słownika Slangu Młodzieżowego (Miejski) i z publikowanych w latach 1935-1937 opowiadań Stefana Wiecheckiego. Pomimo różnic leksykalnych w związkach frazeologicznych tworzonych przez młodzież, należy odnotować uderzające podobieństwa mechanizmów ich tworzenia, zwłaszcza w wykorzystaniu polifonii stylistycznej
Transcendental Continued Fractions
No full textIn the present paper, we give sufficient conditions on the elements of thecontinued fractions and that will assure us that the continued fraction is a transcendental number. With the same condition, we establish atranscendental measure of Comment: 9page
Vers une robotique du traduire – Introduction
No full textL’intelligence artificielle est en train de changer le monde et le rapport que les humains entretiennent avec le travail et concerne les traducteurs au premier chef. La traduction humaine ou biotraduction est-elle en voie d’extinction ? Cette publication dresse un état des lieux provisoire de la question du rôle de l’humain dans l’activité traduisante. En effet, le développement fulgurant de l’intelligence artificielle oblige non seulement les traducteurs professionnels à s’adapter, mais aussi les formations en traduction ainsi que la recherche afférente. Les approches mises en dialogue dans le cadre de cette publication convoquent donc autant l’informatique que la linguistique, la traductologie, la traduction et la didactique des langues
Understanding how systemic change happens -marketisation and de-marketisation
No full textThis paper discusses possible conceptual foundations of formal models of endogenous change processes, understood here as movements between market and non-market transactions at the level of the national economy. It links but does not merge movements of resources with shifts in the pattern of transaction types. In focussing on transaction types, it deploys insights from Commons, Coase, and Godelier, to discuss how framing transaction types as the fundamental 'thing to be explained' points to the value of choices about how activity may best be organised, which requires a general concept, which can be found in Commons' 'going concern', applicable to transactions focussing on markets or not. It entails the possibility of institutional change and shifts in the location of economic resources without formal policy change. It suggests that the main requirement for such change processes are dualistic incentive patterns that operate upon institutional choice and/or development, which derive at root from experienced contrasts between the realities of existing and normatively privileged systems, and others, normatively initially deemed inferior, that offer key actors greater economic efficiency. Moves of institutional activity from one to the other are thus conceptually processes of endogenous systemic change. System in this sense is thus viewed as a coexistence of alternatives. The motivation comes directly from consideration of two very different historical moments: endogenously driven shifts 'from plan to market' in countries attempting central planning, and contemporary pressures in market economies from areas of the economy, such as services, where joint production and/or own consumption imply irremediable market failure and so non-market based economic institutions offer greater economic efficiency and may therefore attract both resources (factors of production) and investment in development of suitable transactions and their organisation
A categorical framework for congruence of applicative bisimilarity in higher-order languages
No full textApplicative bisimilarity is a coinductive characterisation of observationalequivalence in call-by-name lambda-calculus, introduced by Abramsky (1990).Howe (1996) gave a direct proof that it is a congruence, and generalised theresult to all languages complying with a suitable format. We propose acategorical framework for specifying operational semantics, in which we provethat (an abstract analogue of) applicative bisimilarity is automatically acongruence. Example instances include standard applicative bisimilarity incall-by-name, call-by-value, and call-by-name non-deterministic-calculus, and more generally all languages complying with a variantof Howe's format
Distributed Asynchronous Games With Causal Memory are Undecidable
No full textWe show the undecidability of the distributed control problem when the plantis an asynchronous automaton, the controllers use causal memory and the goal ofthe controllers is to put each process in a local accepting state