Temporal logic with cyclic counting and the degree of aperiodicity of finite automata

We define the degree of aperiodicity of finite automata and show that for every set M of positive integers, the class QAM 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...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Ésik Zoltán
Ito Masami
Testületi szerző: Conference for PhD Students in Computer Science (3.) (2002) (Szeged)
Dokumentumtípus: Cikk
Megjelent: 2003
Sorozat:Acta cybernetica 16 No. 1
Kulcsszavak:Számítástechnika, Kibernetika, Automaták
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12705
LEADER 01889nab a2200241 i 4500
001 acta12705
005 20220615084838.0
008 161015s2003 hu o 0|| eng d
022 |a 0324-721X 
040 |a SZTE Egyetemi Kiadványok Repozitórium  |b hun 
041 |a eng 
100 1 |a Ésik Zoltán 
245 1 0 |a Temporal logic with cyclic counting and the degree of aperiodicity of finite automata  |h [elektronikus dokumentum] /  |c  Ésik Zoltán 
260 |c 2003 
300 |a 1-28 
490 0 |a Acta cybernetica  |v 16 No. 1 
520 3 |a We define the degree of aperiodicity of finite automata and show that for every set M of positive integers, the class QAM 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 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. 
650 4 |a Természettudományok 
650 4 |a Számítás- és információtudomány 
695 |a Számítástechnika, Kibernetika, Automaták 
700 0 1 |a Ito Masami  |e aut 
710 |a Conference for PhD Students in Computer Science (3.) (2002) (Szeged) 
856 4 0 |u http://acta.bibl.u-szeged.hu/12705/1/cybernetica_016_numb_001_001-028.pdf  |z Dokumentum-elérés