Topologies, continuity and bisimulations
Topologies, Continuity and Bisimulations
The notion of a bisimulation relation is of basic importance in many areas of computation theory and logic. Of late, it has come to take a particular significance in work on the formal analysis and verification of hybrid control systems, where system properties are expressible by formulas of the modal μ-calculus or weaker temporal logics. Our purpose here is to give an analysis of the concept of bisimulation, starting with the observation that the zig-zag conditions are suggestive of some...
Tours de Hanoï et automates
Toward a semantics for the QUEST language
Towards a logic of semiotic systems
The rationalistic denotational approach to semantics is not adequate for capturing the structural dimension of meaning, which is immanent in semiotic systems. The demand for a structural approach to semantics is intensified by a turn in Artificial Intelligence, introduced by Connectionism and Information Retrieval. This paper presents such a structural approach to semantics founded on the phenomenological and autopoietic paradigms and proposes a formalization with the help of category theory.
Towards a sketch based model of self-interpreters
Towards an integrated theory of formal and natural languages
Towards applying computational complexity to foundations of physics.
Towards automated proofs of observational properties.
Trace languages defined by regular string languages
Traces of term-automatic graphs
In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state...
Tractability of multivariate problems for weighted spaces of functions
We survey recent results on tractability of multivariate problems. We mainly restrict ourselves to linear multivariate problems studied in the worst case setting. Typical examples include multivariate integration and function approximation for weighted spaces of smooth functions.
Transcendence, automata theory and gamma functions for polynomial rings
Transcendental numbers having explicit -adic and Jacobi-Perron expansions
Transducing by observing length-reducing and painter rules
The recently introduced model of transducing by observing is compared with traditional models for computing transductions on the one hand and the recently introduced restarting transducers on the other hand. Most noteworthy, transducing observer systems with length-reducing rules are almost equivalent to RRWW-transducers. With painter rules we obtain a larger class of relations that additionally includes nearly all rational relations.
Transducteurs finis d'arbres et tests d'égalité
Transductions algébriques
Transductions des langages de Chomsky
La feuille des applications dites -transductions, et qu’il serait légitime d’appeler applications rationnelles, d’un monoïde libre dans un autre monoïde est étudiée de façon systématique. L’intérêt de ces applications vient de ce qu’elles transportent partie algébrique (ou -langages) sur partie algébrique, partie rationnelle (ou -langage) sur partie rationnelle. On étudie sous le nom de langage compilable les parties algébriques qu’une -transduction univoque applique dans un ensemble de Dyck...
Transductions et familles de langages
Transductions rationnelles décroissantes