Infinity problems and countability problems for -automata

DOI10.1016/J.IPL.2006.06.011zbMATH Open1185.68400OpenAlexW2077572182MaRDI QIDQ845856FDOQ845856

Authors: Yunfeng Tao 

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.06.011

Recommendations

• \(k\)-counting automata
• Some problems in automata theory which depend on the models of set theory
• Decision problems for Turing machines
• Highly Undecidable Problems For Infinite Computations
• The Complexity of Infinite Computations In Models of Set Theory

zbMATH Keywords

complexityformal languagescardinality\(\omega \)-automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Space-bounded reducibility among combinatorial problems
• Descriptive complexity: a logician's approach to computation.
• Title not available (Why is that?)
• ω-Automata

Cited In (8)

• Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words
• First-order and counting theories ofω-automatic structures
• Counting Multiplicity over Infinite Alphabets
• Title not available (Why is that?)
• Morphisms on infinite alphabets, countable states automata and regular sequences
• Decidability conditions for problems about automata reading infinite words
• \(k\)-counting automata
• Some problems in automata theory which depend on the models of set theory

This page was built for publication: Infinity problems and countability problems for \(\omega \)-automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845856)