Büchi context-free languages

DOI10.1016/j.tcs.2010.11.026zbMath1206.68171MaRDI QIDQ627181

Zoltán Ésik, Szabolcs Iván

Publication date: 21 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.026

zbMATH Keywords

context-free languages; Büchi acceptance condition; countable words; Müller acceptance condition

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

OPERATIONAL CHARACTERIZATION OF SCATTERED MCFLs, ON CONTEXT-FREE LANGUAGES OF SCATTERED WORDS, THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE, Logic for \(\omega\)-pushdown automata, MSO-definable Properties of Muller Context-Free Languages Are Decidable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Automata on linear orderings
• The monadic second order theory of all countable ordinals
• Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
• Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
• Finite automata and ordinals
• The equational theory of regular words
• Tree acceptors and some of their applications
• Weak Second‐Order Arithmetic and Finite Automata
• Context-Free Languages of Countable Words
• Logic and Rational Languages of Words Indexed by Linear Orderings
• On frontiers of regular trees
• Axiomatizing omega and omega-op powers of words
• LINEAR LANGUAGES OF FINITE AND INFINITE WORDS
• Developments in Language Theory
• Generalized finite automata theory with an application to a decision problem of second-order logic
• $ℵ_0$-categoricity of linear orderings
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Long words: The theory of concatenation and \(\omega\)-power