scientific article; zbMATH DE number 3238653
From MaRDI portal
Publication:5526125
zbMath0148.00804MaRDI QIDQ5526125
N. Chomsky, Schützenberger, Marcel-Paul
Publication date: 1963
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Self-avoiding walks and multiple context-free languages, On Boolean closed full trios and rational Kripke frames, Holonomic functions and their relation to linearly constrained languages, Consensus Game Acceptors, Zeta Functions of Formal Languages, Unnamed Item, Quasi-realtime languages, Finite turns and the regular closure of linear context-free languages, On the equivalence of linear conjunctive grammars and trellis automata, On differentiation functions, structure functions, and related languages of context-free grammars, Equations in virtually abelian groups: Languages and growth, An experimental ambiguity detection tool, On the conjecture \(\mathcal {L}_{\mathsf {DFCM}}\subsetneq \mathsf {RCM}\), The language of self-avoiding walks, On doubly symmetric Dyck words, Unnamed Item, Unnamed Item, Greibach normal form for \(\omega\)-algebraic systems and weighted simple \(\omega\)-pushdown automata, Non-closure under complementation for unambiguous linear grammars, Cogrowth series for free products of finite groups, Reducing the local alphabet size in tiling systems by means of 2D comma-free codes, Conjugacy languages in virtual graph products, Unnamed Item, Groups whose word problems are accepted by abelian \(G\)-automata, Unnamed Item, Chomsky-Schützenberger Type Characterizations of Poly-Slender and Parikh Slender Context-Free Languages1 1Work supported by the Grants-in Aid for Scientific Research No. 1 0440034, Japan Society for the Promotion of Sciences and the Dirección General de Enseñanza Superior e Investigación Cientifica, SB 97-00110508, Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats, Coding by minimal linear grammars, On the Commutative Equivalence of Algebraic Formal Series and Languages, Dyck Words, Pattern Avoidance, and Automatic Sequences, Balanced-by-Construction Regular and ω-Regular Languages, Normal forms for elements of the *-continuous Kleene algebras \(K{\otimes_\mathcal{R}}C_2'\), A provably stable neural network Turing machine with finite precision and time, On the Degree of Extension of Some Models Defining Non-Regular Languages, Formulae and Asymptotics for Coefficients of Algebraic Functions, Weighted Logics for Nested Words and Algebraic Formal Power Series, Unnamed Item, Recent advances on reachability problems for valence systems (invited talk), On a class of poly-context-free groups generated by automata, On the group memory complexity of extended finite automata over groups, Unnamed Item, Sur divers produits de séries formelles, Multilinear representations of free pros, On bounded linear codes and the commutative equivalence, Fast uniform analysis of Coupled-Context-Free languages, Applications of L systems to group theory, Context-free grammars with lookahead, Consensus Game Acceptors and Iterated Transductions, Regular languages and their generating functions: The inverse problem, On Rough Approximations of Languages under Infinite Index Indiscernibility Relations, Two-Sided Strictly Locally Testable Languages, On generating series of finitely presented operads, A technology for reverse-engineering a combinatorial problem from a rational generating function, A Revision of Coding Theory for Learning from Language, Definability of Combinatorial Functions and Their Linear Recurrence Relations, The growth function of context-free languages, Analyzing ambiguity of context-free grammars, An ambiguity hierarchy of weighted context-free grammars, Free profinite locally idempotent and locally commutative semigroups, On some transformations in context-free grammars and languages, Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet, Epsilon-reducible context-free languages and characterizations of indexed languages, Weighted automata with storage, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Reduktionssätze über eine Klasse formaler Sprachen mit endlich vielen Zuständen, Gröbner methods for representations of combinatorial categories, Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems, AFL with the semilinear property, Locally testable languages, A homomorphism theorem for weighted context-free grammars, Non recursive functions have transcendental generating series, Sur la rationalite de certaines séries generatrices, Combinatorial specifications for juxtapositions of permutation classes, Linguistic matrix theory, Unnamed Item, Growth and ergodicity of context-free languages II: The linear case, Invito alla teoria dei linguaggi formali, Fonctionnelles causales non linéaires et indéterminées non commutatives, The dual of concatenation, On the simplest centralizer of a language, Context-free coalgebras, Categorial dependency grammars, Random Generation for Finitely Ambiguous Context-free Languages, An algebraic representation of the fixed-point closure of *-continuous Kleene algebras – A categorical Chomsky–Schützenberger theorem, Growth and ergodicity of context-free languages, On the closure properties of linear conjunctive languages., On the Chomsky and Stanley's homomorphic characterization of context-free languages, On solving star equations, Some permutations on Dyck words, Asymptotic approximation by regular languages, Balanced-by-construction regular and \(\omega \)-regular languages, Maximum likelihood analysis of the Ford-Fulkerson method on special graphs, Analytic models and ambiguity of context-free languages, Boolean grammars, Algebraic languages and polyominoes enumeration, On the context-freeness of the set of words containing overlaps, Self-modifying finite automata: An introduction, Context-free languages and random walks on groups, Slender 0L languages, On the language of primitive words, On parsing coupled-context-free languages, LR(k)-coupled-context-free grammars, Thin and slender languages, Prefixes of infinite words and ambiguous context-free languages, Computational aspects of sturdy and flimsy numbers, An ambiguity hierarchy of weighted context-free grammars, Growth in higher Baumslag-Solitar groups, On the number of nonterminals in linear conjunctive grammars, The origins of combinatorics on words, On the rational subset problem for groups., Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy, Computing abstract decorations of parse forests using dynamic programming and algebraic power series, A representation theorem for (\(q\)-)holonomic sequences, Generalized algebraic structures for the representation of discrete systems, On the complexity of the cogrowth sequence, On some properties of very pure codes, Permutations generated by token passing in graphs, Restrictions and representations of vector controlled concurrent system behaviours, Automates a file, The conjugacy growth of the soluble Baumslag-Solitar groups, Langages sur des alphabets infinis, Operatorenkalkül über freien Monoiden I: Strukturen, Enumeration d'arbres et formules d'inversion de séries formelles, Counting problems and algebraic formal power series in noncommuting variables, Adherences of languages, Algebras of linear growth and the dynamical Mordell-Lang conjecture, Queues, stacks, and transcendentality at the transition to chaos, Growth-sensitivity of context-free languages., Scheduling hard sporadic tasks with regular languages and generating functions., A new algorithm for regularizing one-letter context-free grammars., Growth properties of power-free languages, Grammar semantics, analysis and parsing by abstract interpretation, Context-free pairs of groups. II: Cuts, tree sets, and random walks, Automatic average-case analysis of algorithms, On the commutative equivalence of bounded context-free and regular languages: the code case, The complexity of computing the number of strings of given length in context-free languages, Random generation of words in an algebraic language in linear binary space, Theory of reaction automata: a survey, Valuations of languages, with applications to fractal geometry, On the computing powers of \(\mathcal{L}\)-reductions of insertion languages, Colored operads, series on colored operads, and combinatorial generating systems, A unifying approach to algebraic systems over semirings, On pairs of non-crossing generalized Dyck paths, Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern, Progress in free associative algebras, One counter languages and the IRS condition, Reversal-bounded multipushdown machines, Transductions des langages de Chomsky, Sequentielle Analyse kontextfreier Sprachen, Context-free grammar forms, First-order logics: some characterizations and closure properties, A representation theorem of infinite dimensional algebras and applications to language theory, Equivalence problems for deterministic context-free languages and monadic recursion schemes, Inference for regular bilanguages, On a class of languages with holonomic generating functions, Classifying lattice walks restricted to the quarter plane, Three efficient algorithms for counting problems, Formal languages and enumeration, Bi-inductive structural semantics, Twin-roots of words and their properties, From decidability to undecidability by considering regular sets of instances, On regularity of context-free languages, Approximate minimization of weighted tree automata, Transcendence of binomial and Lucas' formal power series, A note on context-free languages, Automata and rational expressions, Finite transducers and rational transductions, Enumerating regular expressions and their languages, An example of an indexed language of intermediate growth, Extracting symbolic knowledge from recurrent neural networks -- a fuzzy logic approach, Maximum likelihood analysis of algorithms and data structures, Transcendence of formal power series with rational coefficients, Ambiguity and decision problems for local adjunct languages, Equivalenza tra grammatiche, sistemi di equazioni in variabili di linguaggio e serie formali, \(L(A)=L(B)\)? decidability results from complete formal systems, Cyclic derivation of noncommutative algebraic power series, Insertion languages, Motif statistics., A homomorphic characterization of recursively enumerable languages, Closure properties of slender languages, On the number of factors of Sturmian words, Diagram groups and directed 2-complexes: homotopy and homology., wMSO theories as grammar formalisms, Efficient enumeration of regular expressions for faster regular expression synthesis, On the growth of linear languages
