Temporal Logic with Cyclic Counting and the Degree of Aperiodicity of Finite Automata

Zoltán Ésik
Masami Ito

December 2001


We define the degree of aperiodicity of finite automata and show that for every set $M$ of positive integers, the class ${\bf QA}_M$ of finite automata whose degree of aperiodicity belongs to the division ideal generated by $M$ is closed with respect to direct products, disjoint unions, subautomata, homomorphic images and renamings. These closure conditions define q-varieties of finite automata. We show that q-varieties are in a one-to-one correspondence with literal varieties of regular languages. We also characterize ${\bf QA}_M$ as the cascade product of a variety of counters with the variety of aperiodic (or counter-free) automata. We then use the notion of degree of aperiodicity to characterize the expressive power of first-order logic and temporal logic with cyclic counting with respect to any given set $M$ of moduli. It follows that when $M$ is finite, then it is decidable whether a regular language is definable in first-order or temporal logic with cyclic counting with respect to moduli in $M$

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.