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 (46)
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
This page was built for publication: Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
