PCSC 2008: Dr. Henry Adorna

PCSC 2008
8th Philippine Computing Science Congress
23 - 24 February 2008
University of the Philippines-Diliman
Quezon City, Philippines
Organized by: Computing Society of the Philippines (CSP)
Tel. +63 2 7090907, +63 2 4266125
E-mail: computingsoc@gmail.com
Website: http://www.csp.org.ph
=================================================

On Sequences, Languages, and Automata


Henry N. Adorna, Ph.D.
Department of Computer Science
(Algorithms and Complexity)
University of the Philippines-Diliman
Quezon City, Philippines
henri@csp.org.ph

ABSTRACT

Automata theoryis one ofthe oldest and most simplest computing model investigated in theoretical computer science. Words and languages are the basic building blocks in studying automata theory. For the last ten years or so, efforts to put automata theory in the main stream of computer science research has been the goal of most formal languages and automata theorists. There are conferences organized every year as venue to new results in automata and formal languages theory. These, indeed contribute significantly in placing automata theory approxiamately near where it was some half a century ago.

In thispaper, we report on some results based on the work of the author and his collaborators on properties of some new finite automaton accepting regular languages. In particular, we consider questions about characterization and state complexities of this finite automaton. We also report on a new regular language preserving operation. A deterministic finite automaton with output(dfao) considered as another way of looking at cosets coloring of n-dimensional objects or patterns. Finally, we present a reasonable generalization of a so-called k-automatic sequence, which we call k-context-free sequence.

Keywords: Sequences, Languages, Automata, Cosets, Coloring