Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
From MaRDI portal
Publication:1240574
DOI10.1016/S0022-0000(77)80004-4zbMath0363.68113OpenAlexW2022934640MaRDI QIDQ1240574
Publication date: 1977
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(77)80004-4
Related Items
On omega context free languages which are Borel sets of infinite rank., Specification and verification of decentralized daisy chain arbiters with \(\omega\)-extended regular expressions, Merging regular processes by means of fixed-point theory, There is no fully abstract fixpoint semantics for non-deterministic languages with infinite computations, Somewhat finite approaches to infinite sentences., Unnamed Item, Unnamed Item, Characterization and closure properties of linear \(\omega\)-languages, Output concepts for accelerated Turing machines, Greibach normal form for \(\omega\)-algebraic systems and weighted simple \(\omega\)-pushdown automata, On the complexity of \(\omega\)-type Turing acceptors, Ambiguity in omega context free languages, The Triple-Pair Construction for Weighted ω-Pushdown Automata, A hierarchy of deterministic context-free \(\omega\)-languages., Borel hierarchy and omega context free languages., Büchi context-free languages, Constrained properties, semilinear systems, and Petri nets, Adherences of languages, Unnamed Item, Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank, Unnamed Item, Distributed ω-Automata, Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra, Affine automata and related techniques for generation of complex images, Rational and affine expressions for image description, Infinite behaviour of Petri nets, Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition, Topological properties of omega context-free languages, Wadge hierarchy of omega context-free languages, \(\omega\)-computations on Turing machines, Unnamed Item, \(\omega\)-computations on deterministic pushdown machines, Logic for \(\omega\)-pushdown automata, MSO-definable Properties of Muller Context-Free Languages Are Decidable, On Müller context-free grammars, ON CONTEXT-FREE LANGUAGES OF SCATTERED WORDS, Alternating Context-Free Languages and Linear Time μ-Calculus with Sequential Composition, OPERATIONAL CHARACTERIZATION OF SCATTERED MCFLs, Real functions and numbers defined by Turing machines, Finite-state \(\omega\)-languages, Init and Anf operating on \(\omega\)-languages, Alternating finite automata on \(\omega\)-words, Infinite arrays and controlled deterministic table 0L array systems, On infinite words obtained by selective substitution grammars, Safety and liveness of \(\omega\)-context-free languages, Description and reasoning of VLSI circuit in temporal logic
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Theories of automata on \(\omega\)-tapes: a simplified approach
- Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition
- \(\omega\)-computations on Turing machines
- \(\omega\)-computations on deterministic pushdown machines
- Time-restricted sequence generation
- On the Computational Complexity of Algorithms
- Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
- Sets of Numbers Defined by Finite Automata
- Decision problems forω-automata
- Decision methods in the theory of ordinals
- Definability in the monadic second-order theory of successor
- Testing and generating infinite sequences by a finite automaton
- Decidability of Second-Order Theories and Automata on Infinite Trees
