Deterministic context free languages

DOI10.1016/S0019-9958(66)80019-0zbMath0145.00802MaRDI QIDQ5521476

Sheila A. Greibach, Seymour Ginsburg

Publication date: 1966

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

mathematical logic

Related Items (92)

The effect of end-markers on counter machines and commutativity ⋮ The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes ⋮ The theory of languages ⋮ A pumping lemma for real-time deterministic context-free languages ⋮ One-counter pushdown-storage automata as transducers of sequences ⋮ A universal compiler system based on production rules ⋮ An approach to deciding the observational equivalence of Algol-like languages ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ Input-driven languages are linear conjunctive ⋮ The theory of languages ⋮ Syntax checking either way ⋮ Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages ⋮ The equivalence problem for deterministic pushdown automata is decidable ⋮ Unnamed Item ⋮ Deletion operations on deterministic families of automata ⋮ Unnamed Item ⋮ Aspects of Reversibility for Classical Automata ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ Outfix-guided insertion ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ One-way weak-stack-counter automata ⋮ Generalized overlap resolvable grammars and their parsers ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats ⋮ Achievable high scores of \(\varepsilon\)-moves and running times in DPDA computations ⋮ A Note on Pushdown Store Automata and Regular Systems ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ A hierarchy of deterministic context-free \(\omega\)-languages. ⋮ Formal grammars for turn-bounded deterministic context-free languages ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract) ⋮ The Hardest LL(k) Language ⋮ Stochastic grammars and languages ⋮ On the complexity of regular-grammars with integer attributes ⋮ \(\mathrm{GF}(2)\)-operations on basic families of formal languages ⋮ On the Density of Context-Free and Counter Languages ⋮ Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata ⋮ The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine ⋮ On LLP(k) grammars and languages ⋮ Quasi-rocking real-time pushdown automata ⋮ The Boolean closure of linear context-free languages ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ The inclusion problem for some subclasses of context-free languages ⋮ Necessary and sufficient conditions for a power language to be deterministic ⋮ Accepting runs in a two-way finite automaton ⋮ Reversible pushdown automata ⋮ On the degrees of non-regularity and non-context-freeness ⋮ An improved bound for detecting looping configurations in deterministic PDA's ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Unions of certain bounded deterministic languages ⋮ Decidability of DPDA equivalence ⋮ Transductions des langages de Chomsky ⋮ Simple context-free languages and free monadic recursion schemes ⋮ On jump-deterministic pushdown automata ⋮ Syntax checking either way ⋮ Comparing language operations ⋮ Finite automata with multiplication ⋮ Temporal logics with language parameters ⋮ Normal forms of deterministic grammars ⋮ Equivalence problems for deterministic context-free languages and monadic recursion schemes ⋮ A strong pumping lemma for context-free languages ⋮ A decidability result for deterministic \(\omega\)-context-free languages ⋮ On LR(k) grammars and languages ⋮ On store languages of language acceptors ⋮ On inverse deterministic pushdown transductions ⋮ Nondeterminism and Boolean operations in pda's ⋮ \(\omega\)-computations on deterministic pushdown machines ⋮ State Complexity of the Quotient Operation on Input-Driven Pushdown Automata ⋮ On equivalence and subclass containment problems for deterministic context-free languages ⋮ A note on non-singular deterministic pushdown automata ⋮ Refining nondeterminism in context-free languages ⋮ A note on cyclic closure operations ⋮ On equivalence of grammars through transformation trees ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ Deterministic stack automata and the quotient operator ⋮ Outfix-Guided Insertion ⋮ Properties of syntax directed translations ⋮ Intersections de langages algébriques bornes ⋮ Decidability of the equivalence problem for deterministic pushdown automata ⋮ Une généralisation des ensembles de Dyck ⋮ Error detection in formal languages ⋮ On the relation between the class of all context-free languages and the class of deterministic context-free languages ⋮ LR-regular grammars - an extension of LR(k) grammars ⋮ HOMOMORPHISMS PRESERVING DETERMINISTIC CONTEXT-FREE LANGUAGES ⋮ Strict deterministic grammars ⋮ Sur une propriété d'itération des langages algébriques déterministes ⋮ Infinite regular Thue systems ⋮ Invito alla teoria dei linguaggi formali ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ A note on chains of deterministic pushdown transducers ⋮ A note on undecidable properties of formal languages ⋮ Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems

This page was built for publication: Deterministic context free languages