Invited Speakers

Philippe SchnoebelenLaure Daviaud
Philippe schnoebelen is Directeur de recherche CNRS & Professeur attaché ENS Paris-Saclay. Laure Daviaud Lecturer in Computer Science at City University of London.
Title: Reasoning about subwords and subsequences Title: Weighted automata: To be decidable, or not to be decidable, that is the question.

Abstract:  In language theory, a subsequence of a word is called a subword (or sometimes a scattered subword) and should not be confused with a factor which is a contiguous block of letters extracted from the original word.
Subwords do not behave as nicely as factors and many interesting problems in logic, automata theory, and algorithmics are harder for subwords than for factors. In this talk I shall consider several instances of this phenomenon, present some recent results and offer some open problems.

Abstract: In this talk, I will first give a broad overview of decidability problems for weighted automata, what is known, and what is still open. I will then focus on a specific recent result and explain the decision procedure for the Big-O problem for max-plus automata.

Comments are closed.