Algorithms are inherently deterministic. Here is a famous nondeterministic algorithm: “When you come to a fork in the road, take it,” by Yogi Berra, the American baseball player and unlicensed philosopher. In our view, “nondeterministic algorithm” is a contradiction in terms. Yet people speak about probabilistic algorithms and quantum algorithms. Does that contradict our contention that algorithms are inherently deterministic? Our thesis is that non-algorithmic work, from tossing a coin to quantum measurement, is done by assistants, partners, oracles, and other interactants. We axiomatize assisted algorithms, define assisted abstract state machines, and prove that every assisted algorithm is faithfully simulated step-by-step by an appropriate assisted abstract state machine. One of our running examples comes from quantum computing, but no knowledge of quantum computing is assumed.
Tentative title. Abstract to be announced.
On the problem of the definition of the star of a series
Working with weighted automata naturally leads to the problem of the definition of the (Kleene) star operation on the semiring of (formal power) series. And proving that rational series are realised by weighted finite automata (one direction of Kleene Theorem) requires, in one way or another, to establish the identity: (s₀ + sₚ)* = (s₀)* (sₚ (s₀)*)* where s₀ and sₚ are respectively the 'constant term' and the 'proper part' of a series s.
In my book 'Elements of Automata Theory', I gave a proof of the above identity under the hypothesis that the weight semiring has the property that the product of two summable families is a summable family. I called such semirings 'strong' and even though all semirings that I knew are strong, I stated the conjecture that there should exist some semirings which are not strong.
In this talk, and after setting the framework of the topological approach to the definition of star and recalling the proof of the quoted theorem, I present a construction that provides an example of a topological semiring — a Banach algebra indeed — which is not strong.
Joint work with David Madore (LTCI - Télécom Paris, IPP)
Biomedical observations often acquire their meaning through relations in space and time: an event persists for a specified duration, one event follows another within a given interval, or an imaged structure lies near a particular anatomical region. Expressing these relations precisely, and using the same definitions across records and datasets, is a central concern of biomedical informatics. It also provides a natural setting for questions about logical representation, expressiveness and computation.
I will introduce Ensemble Logic (EL), a family of modal logics interpreted over metric monoids: commutative monoids equipped with translation-invariant metrics. Its three modal operators express displacement, bounded existence and bounded universality. Quantification over points and lengths allows the same parameter to constrain several parts of a formula, so that, for example, successive phases of a temporal pattern can be required to have equal duration. The framework accommodates discrete and dense time, spatial domains and their products. In suitable spatial interpretations, the operators correspond to translocation, dilation and erosion of the sets where formulas hold.
I will then discuss Symbolic Biomedicine: a program to represent biomedical knowledge as explicit, compositional statements that can be queried, checked and reused, using EL. An annotated record supplies an interpretation, a formula specifies a pattern of interest, and model checking determines where the pattern occurs. Building on applications to temporal records, EL for biomedical images, for example, asks how proximity, containment and change can be expressed and evaluated in two and three spatial dimensions and over time. These questions connect the logical foundations to open problems in geometric representation, computational tractability and the preservation of biomedical meaning. No prior background in medicine or biomedical informatics will be assumed.
We consider decision problems for Boolean combinations of omega-rational trace languages. The complexities of these decision problems (emptiness, regularity, rationality) are classified depending on properties of the independence alphabets and of the Boolean combinations allowed. For any of the problems, we obtain a trichotomy ranging from decidable over a low level of the arithmetical hierarchy to a low level of the analytical hierarchy.
Title and abstract to be announced.
I shall outline some of the steps in the proposed classification of all the countable homogeneous ordered multipartite graphs (work in progress, joint with David Bradley-Williams). So far in work with Jenkinson and Seidel we have a classification in the unordered case, and also a classification in the ordered case for bipartite graphs. I focus mainly on the bipartite and tripartite cases, but also touch on how the general proof may go.
Title and abstract to be announced.
Title and abstract to be announced.
Fagin's seminal result characterizing NP in terms of existential second-order logic started the fruitful field of descriptive complexity theory. In recent years, there has been much interest in the investigation of quantitative (weighted) models of computations. In this talk I will present a study of descriptive complexity based on weighted Turing machines over arbitrary semirings. We provide machine-independent characterizations (over ordered structures) of several weighted complexity in terms of definability in suitable weighted logics for an arbitrary semiring. In particular, we prove weighted versions of Fagin's theorem (even for arbitrary structures, not necessarily ordered, provided that the semiring is idempotent and commutative), the Immerman-Vardi's theorem (originally for P) and the Abiteboul-Vianu-Vardi's theorem (originally for PSPACE). After that, I will discuss another machine model (Semiring Turing Machines) that also incorporates quantitative information in computations improving on some earlier limitations in the model from Eiter & Kiesel (Semiring Reasoning Frameworks in AI and Their Computational Complexity, J. Artif. Intell. Res., 2023). We solve an open problem proposed in Eiter & Kiesel by providing a Fagin-style theorem for the quantitative version of the complexity class NP, using another version of weighted existential second-order logic that allows predicates to be interpreted as semiring-annotated relations.
Title and abstract to be announced.
Abstract to be announced.