Asymptotic Approximation by Regular Languages (YR-OWLS)

Abstract: In this talk we will introduce a new property of formal languages called REG-measurability where REG is the class of regular languages. Intuitively, a language L is REG-measurable if there exists an infinite sequence of regular languages that ``converges'' to L. A language without REG-measurability has a complex shape in some sense so that it can not be approximated by regular languages.

The motivation, why we have been interested in REG-measurability, originally came from the following conjecture posed by [Dömösi-Horvath-Ito 1991]: the set of all primitive words over a non-singleton alphabet is not context-free.

We will describe that several context-free languages are REG-measurable (including languages with transcendental generating function and transcendental density, in particular), while a certain simple deterministic context-free language and the set of primitive words are REG-immeasurable in a strong sense. We will also discuss some open problems and future work. This talk is based on the following work: www.math.akita-u.ac.jp/~ryoma/misc/measure.pdf

formal languages and automata theorylogic in computer sciencelogic

Audience: researchers in the discipline

( paper )

---

Online Worldwide Seminar on Logic and Semantics (OWLS)

Series comments: The Online Worldwide Seminar on Logic and Semantics is a new series of research talks, highlighting the most exciting recent work in the international computer science logic community. The scope of the seminar series is roughly that of the major computer science logic conferences such as LICS, ICALP and FSCD. It takes place on most Wednesdays, with a focus every other week on the work of young researchers.

In this time of restricted international travel, a key aim of this series is to provide a forum for the informal discussion and social interaction that is so important for the progress of science. To facilitate this, the seminar incorporates in virtual form a number of features more normally associated with physical meetings.

For more details, please visit the homepage. There is no need to register for the talks, just show up.

---