Jürgen Dassow

Descriptional Complexity and Operations - Two Non-Classical Cases

In the talk we study the behaviour of some complexity measures if operations (union, complement, product, star, etc.) are applied to languages. Read More ›

by Jürgen Dassow (Otto von Guericke University Magdeburg, Germany)

Dora Giammarresi

Avoiding Overlaps in Pictures

Pictures are a generalization of strings to two dimensions and they are represented by two-dimensional (rectangular) arrays of symbols taken from a finite alphabet $\Sigma$. Extending results from the formal string language theory to two dimensions is a very challenging task. Read More ›

by Dora Giammarresi (University of Rome Tor Vergata, Italy)

Orna Kupferman

Sensing as a Complexity Measure

The size of deterministic automata required for recognizing regular and $\omega$-regular languages is a well-studied measure for the complexity of languages. We introduce and study a new complexity measure, based on the sensing required for recognizing the language. Read More ›

by Orna Kupferman (The Hebrew University, Jerusalem, Israel)

Stavros Konstantinidis

Applications of Transducers in Independent Languages, Word Distances, Codes

A (nondeterministic) transducer $t$ is an operator mapping an input word to a set of possible output words. A few types of transducers are important in this work: input-altering, input-preserving, input-decreasing. Read More ›

by Stavros Konstantinidis (Saint Mary's University, Halifax/NS, Canada)