On Context-Free Languages
From MaRDI portal
Publication:5534924
DOI10.1145/321356.321364zbMath0154.25801OpenAlexW2157390113MaRDI QIDQ5534924
Publication date: 1966
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321356.321364
Related Items (max. 100)
Counter machines and counter languages ⋮ Context-Freeness of Word-MIX Languages ⋮ Enumerating Restricted Dyck Paths with Context-Free Grammars ⋮ A New Operator over Parikh Languages ⋮ Abelian Repetitions in Sturmian Words ⋮ On spectra of sentences of monadic second order logic with counting ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Jumping automata over Infinite words ⋮ Algebraic and context-free subsets of subgroups ⋮ Testing membership for timed automata ⋮ On the existential arithmetics with addition and bitwise minimum ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Hairpin completions and reductions: semilinearity properties ⋮ Abelian combinatorics on words: a survey ⋮ Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata ⋮ The effect of jumping modes on various automata models ⋮ Parikh Matrices: Subword Indicators and Degrees of Ambiguity ⋮ Algebraic properties of Parikh \texttt{q}-matrices on two-dimensional words ⋮ Simulation by Rounds of Letter-to-Letter Transducers ⋮ Unnamed Item ⋮ A Filtering Technique for All Pairs Approximate Parameterized String Matching ⋮ INTERLEAVING LOGIC AND COUNTING ⋮ \(M\)-equivalence of Parikh matrix over a ternary alphabet ⋮ When is context-freeness distinguishable from regularity? An extension of Parikh's theorem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ HOW TO SYNCHRONIZE THE HEADS OF A MULTITAPE AUTOMATON ⋮ Reducing the ambiguity of Parikh matrices ⋮ On the Boundedness Property of Semilinear Sets ⋮ Properties of right one-way jumping finite automata ⋮ CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES ⋮ Properties of graphs specified by a regular language ⋮ One-Way Jumping Finite Automata ⋮ On the Petri net realization of context-free graphs ⋮ Unnamed Item ⋮ Visit-bounded stack automata ⋮ Some Results on the Length of Proofs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Infinitude of Primes Using Formal Languages ⋮ Unnamed Item ⋮ Limited automata and unary languages ⋮ Chrobak Normal Form Revisited, with Applications ⋮ Geometrical Regular Languages and Linear Diophantine Equations ⋮ Scope-Bounded Pushdown Languages ⋮ Strong (2 ⋅ t) and Strong (3 ⋅ t) Transformations for Strong M-Equivalence ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Logic and rational languages of scattered and countable series-parallel posets ⋮ Parikh q-Matrices and q-Ambiguous Words ⋮ Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs. ⋮ Closure properties of synchronized relations ⋮ Unnamed Item ⋮ Comparisons between some pumping conditions for context-free languages ⋮ UNAMBIGUOUS CONSTRAINED AUTOMATA ⋮ The State Complexity of Permutations on Finite Languages over Binary Alphabets ⋮ Groups Whose Word Problem is a Petri Net Language ⋮ On Core Words and the Parikh Matrix Mapping ⋮ A New Study of Parikh Matrices Restricted to Terms ⋮ Decidability of Right One-Way Jumping Finite Automata ⋮ Semilinearity of Families of Languages ⋮ A Fully Equational Proof of Parikh's Theorem ⋮ Approximate consistency for transformations on words and trees ⋮ The effect of end-markers on counter machines and commutativity ⋮ Some decision problems concerning semilinearity and commutation. ⋮ Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ On a conjecture about Parikh matrices ⋮ On computational complexity of graph inference from counting ⋮ Higher-level synchronising devices in Meije-SCCS ⋮ Subword histories and Parikh matrices ⋮ Abelian powers and repetitions in Sturmian words ⋮ Parikh word representable graphs and morphisms ⋮ Catalytic P systems, semilinear sets, and vector addition systems ⋮ Elementary matrix equivalence and core transformation graphs for Parikh matrices ⋮ Algebraic dynamic programming for multiple context-free grammars ⋮ On commutative context-free languages ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ On the language of primitive words ⋮ A note on the expressive power of probabilistic context free grammars ⋮ A theoretical framework for cardinality-based feature models: the semantics and computational aspects ⋮ Document spanners: from expressive power to decision problems ⋮ Subword conditions and subword histories ⋮ Order of weak \(M\)-relation and Parikh matrices ⋮ Several extensions of the Parikh matrix \(L\)-morphism ⋮ On selective unboundedness of VASS ⋮ On the rational subset problem for groups. ⋮ Comparisons of Parikh's condition to other conditions for context-free languages ⋮ Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata ⋮ Similarity in languages and programs ⋮ On the open problem of Ginsburg concerning semilinear sets and related problems ⋮ Complexity of multi-head finite automata: origins and directions ⋮ On vector languages ⋮ Langages sur des alphabets infinis ⋮ Languages as hyperplanes: grammatical inference with string kernels
This page was built for publication: On Context-Free Languages
