Two Families of Languages Related to ALGOL
From MaRDI portal
Publication:5592251
DOI10.1145/321127.321132zbMath0196.01803DBLPjournals/jacm/GinsburgR62OpenAlexW2000118875WikidataQ29037918 ScholiaQ29037918MaRDI QIDQ5592251
Publication date: 1962
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321127.321132
Related Items (63)
The theory of languages ⋮ Correctness of fixpoint transformations ⋮ Language equations over a one-letter alphabet with union, concatenation and star: A complete solution ⋮ Parikh’s Theorem and Descriptional Complexity ⋮ Generating all permutations by context-free grammars in Chomsky normal form ⋮ Boolean grammars ⋮ Equations over sets of integers with addition only ⋮ Periodic sets of integers ⋮ Generating all permutations by context-free grammars in Greibach normal form ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ Characteristics of graph languages generated by edge replacement ⋮ Equivalences and transformations of regular systems - applications to recursive program schemes and grammars ⋮ The theory of languages ⋮ An axiomatic definition of context-free rewriting and its application to NLC graph grammars ⋮ Recursive descent parsing for Boolean grammars ⋮ Language equations with complementation: decision problems ⋮ Aspects of Reversibility for Classical Automata ⋮ Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ The equational logic of fixed points ⋮ A simple P-complete problem and its language-theoretic representations ⋮ Deciding determinism of unary languages ⋮ Proving language inclusion and equivalence by coinduction ⋮ Complexity of equations over sets of natural numbers ⋮ Graph expressions and graph rewritings ⋮ Input- or output-unary sweeping transducers are weaker than their 2-way counterparts ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Generalization of the Ginsburg-Rice Schuetzenberger fixed-point theorem for context-sensitive and recursive-enumerable languages ⋮ Extended regular expressions of star degree at most two ⋮ Description of developmental languages using recurrence systems ⋮ A new algorithm for regularizing one-letter context-free grammars. ⋮ Grammar semantics, analysis and parsing by abstract interpretation ⋮ The inclusion problem for some subclasses of context-free languages ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ Unambiguous Boolean grammars ⋮ Extended regular expressions of arbitrary star degrees ⋮ Unnamed Item ⋮ Computational completeness of equations over sets of natural numbers ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ Decision problems for language equations ⋮ Conjunctive grammars with restricted disjunction ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Conjunctive Grammars with Restricted Disjunction ⋮ Formal languages over GF(2) ⋮ IO and OI. I ⋮ IO and OI. II ⋮ Least and greatest solutions of equations over sets of integers ⋮ Push complexity: optimal bounds and unary inputs ⋮ Generalized sequential machine maps ⋮ Tree acceptors and some of their applications ⋮ Language equations with complementation: expressive power ⋮ Pushdown cellular automata ⋮ Characterization of unary developmental languages ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ The dual of concatenation ⋮ On the Class of Predicates Decidable by Two-Way Multitape Finite Automata ⋮ Extended automata-like regular expressions of star degree at most (2,1) ⋮ Two-sided context specifications in formal grammars ⋮ Some restrictions onW-grammars ⋮ Unresolved systems of language equations: expressive power and decision problems
This page was built for publication: Two Families of Languages Related to ALGOL
