Ambiguity of {\omega}-Languages of Turing Machines

DOI10.2168/LMCS-10(3:12)2014zbMath1337.03056arXiv1209.5669MaRDI QIDQ2878760

Olivier Finkel

Publication date: 5 September 2014

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1209.5669

zbMATH Keywords

Turing machinesformal languagesinfinite wordsmodels of set theoryeffective descriptive set theorydegrees of ambiguityBüchi transition systems

Mathematics Subject Classification ID

Descriptive set theory (03E15) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Related Items (4)

Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words ⋮ Computational capabilities of analog and evolving neural networks over infinite input streams ⋮ Polishness of some topologies related to word or tree automata ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

This page was built for publication: Ambiguity of {\omega}-Languages of Turing Machines