scientific article; zbMATH DE number 3293666
From MaRDI portal
zbMath0184.28401MaRDI QIDQ5576254
Publication date: 1966
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Some decision problems concerning semilinearity and commutation., On omega context free languages which are Borel sets of infinite rank., Computational complexity of synchronization under sparse regular constraints, Algebraic languages and polyominoes enumeration, On the language of primitive words, DM-automata and classes of context-free languages, Network languages for intelligent control, Network languages for concurrent multiagent systems, Cooperation in context-free grammars, Length considerations in context-free languages, The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors, Deterministic multitape automata computations, On vector languages, Controlled pushdown automata, Deque automata, languages, and planar graph representations, Ambiguity in omega context free languages, Borel hierarchy and omega context free languages., Well-abstracted transition systems: Application to FIFO automata., On the equivalence problem of context-free and DT0L languages, On bounded linear codes and the commutative equivalence, Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity, On the commutative equivalence of bounded context-free and regular languages: the semi-linear case, Structure des grammaires d'ambiguite bornee, Multitree automata that count, Reversal-bounded multipushdown machines, Über eine explizite Darstellung von Listenstrukturen, The Turing degree of the inherent ambiguity problem for context-free languages, Transductions des langages de Chomsky, LL-regular grammars, Logical foundations of applied mathematics, Some properties of the class of \(L\) languages with interactions, Monoides syntactiques des langages algébriques, Context-free grammar forms, Automatic generation of lexical analyzers in a compiler-compiler, The inclusion of the substitution closure of linear and one-counter languages in the largest sub-AFL of the family of algebraic languages is proper, Bounded AFLs, Grammarforms and grammarhomomorphisms, On the equivalence, containment, and covering problems for the regular and context-free languages, Max-product grammars and languages, A useful device for showing the solvability of some decision problems, Proving containment of bounded AFL, Some uniformly erasable families of languages, The inclusion problem for simple languages, On proving that certain languages are not ETOL, On the completeness of the inductive assertion method, Commutative grammars, Computation sequence sets, Canonical realization of general time systems, Intercalation lemmas for tree transducer languages, Grammatical characterizations of NPDAs and VPDAs with counters, Augmented transition networks and their relation to tree transducers, Direct or cascade product of pushdown automata, On LR(k) grammars and languages, Economy of description by parsers, DPDA's, and PDA's, Decidable problems on the strong connectivity of Petri net reachability sets, Characteristic parsing: A framework for producing compact deterministic parsers. I, Characteristic parsing: A framework for producing compact deterministic parsers. II, Tree controlled grammars, Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages, Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition, A simplified proof of Parikh's theorem, Single-valued a-transducers, Pushdown acceptor forms, Some relations between Markov algorithms and formal languages, Nondeterminism and Boolean operations in pda's, A representation of trees by languages. I, Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles, Langages algébriques, paires iterantes et transductions rationnelles, Structural pattern recognition, homomorphisms, and arrangements, \(\omega\)-computations on deterministic pushdown machines, Effective constructions in well-partially-ordered free monoids, Counting productions in context-free derivations, Opérations de cylindre et applications séquentielles gauches inverses, Lower bounds on space complexity for contextfree recognition, On splitting recursive sets, On finite-index indexed grammars and their restrictions, Die Verwandtschaft kontextfreier Grammatiken, Générateurs algébriques et systèmes de paires iterantes, On the family of finite index matrix languages, Remarks about commutative context-free languages, Decidability of the equivalence problem for deterministic pushdown automata, Sticker systems, A construction on finite automata that has remained hidden, On quasi orders of words and the confluence property, Morphismes unispectraux. (Unispectral morphisms), Equivalence problems for transducers with a bounded number of states, On lengths of words in context-free languages, Ambiguity and decision problems for local adjunct languages, Left-derivation bounded languages, Equivalenza tra grammatiche, sistemi di equazioni in variabili di linguaggio e serie formali, Normal forms for context-sensitive grammars, Theory of formal grammars, Decidability results concerning \(k\)-limited ED0L systems, A linguistic approach to geometric reasoning, On fault tolerance of syntax, \(\Pi_ 1^ 1\)-universality of some propositional logics of concurrent programs, Iterating transducers, S-arrangements with repetitions, Closure properties of slender languages, Translations of network languages, On the Chomsky and Stanley's homomorphic characterization of context-free languages, Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages, Graph theoretic closure properties of the family of boundary NLC graph languages, On solving star equations, Generating languages by a derivation procedure for elementary formal systems, Rational equivalence relations, On commutative context-free languages, Regulated nondeterminism in pushdown automata, The equivalence problem for deterministic MSO tree transducers is decidable, Bounded D0L languages, Hierarchies of one-way multihead automata languages, Representation and uniformization of algebraic transductions, Theory of traces, Deterministic catalytic systems are not universal, A unified framework for disambiguating finite transductions, Boundedness testing for unambiguous context-free grammars, Finite generation of ambiguity in context-free languages, Sur les générateurs algébriques et linéaires, A transformation system for generating description languages of chain code pictures, Descriptional complexity of bounded context-free languages, Shuffle on trajectories: Syntactic constraints, Comparisons of Parikh's condition to other conditions for context-free languages, Shuffled languages -- representation and recognition, Cônes rationnels commutatifs, On the open problem of Ginsburg concerning semilinear sets and related problems, Complexity of multi-head finite automata: origins and directions, A representation of trees by languages. II, Rational bijection of rational sets, Un théorème de factorisation des produits d'endomorphismes de \(K^N\), Deadlock and fairness in parallel schemas: A set-theoretic characterization and decision problems, On generators and generative capacity of EOL forms, On bounded languages and reversal-bounded automata, Eine neue Invariante für kontextfreie Sprachen, Block insertion and deletion on trajectories, Selective substitution array grammars, On the reachability problem for 5-dimensional vector addition systems, Propositional dynamic logic is weaker without tests, A note on a problem in the theory of grammatical complexity, Descriptional complexity of two-way pushdown automata with restricted head reversals, Position-restricted grammar forms and grammars, Bounded underapproximations, A pushdown automaton or a context-free grammar - which is more economical?, Transformational-generative grammar for description of formal properties, Extended regular expressions of star degree at most two, The (generalized) Post correspondence problem with lists consisting of two words is decidable, Langages satures et cônes decroissants. Langages et cônes bifideles, Growth properties of power-free languages, Grammar semantics, analysis and parsing by abstract interpretation, The Boolean closure of linear context-free languages, On the commutative equivalence of bounded context-free and regular languages: the code case, On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\), Fine covers of a VAS language, Multipass automata and group word problems, Dynamical properties of PWD0L systems, A decision method for Parikh slenderness of context-free languages, Slender Siromoney matrix languages, Extended regular expressions of arbitrary star degrees, The context-freeness of the languages associated with vector addition systems is decidable, Recognising \(k\)-connected hypergraphs in cubic time, Decision problems and regular chain code picture languages, An algebraic semantics for structured transition systems and its application to logic programs, Learning semilinear sets from examples and via queries, Context-free grammars, differential operators and formal power series, On bounded rational trace languages, On 3-head versus 2-head finite automata, A note on semilinear sets and bounded-reversal multihead pushdown automata, A geometric hierarchy of languages, Two iteration theorems for some families of languages, A decidability theorem for a class of vector-addition systems, Two-way A-transducers and AFL, The decidability of a mapping problem for generalized sequential machines with final states, Progress in free associative algebras, L-fuzzy grammars, Natural state transformations, Some independent families of one-letter languages, On the unambiguity of n-tuple languages, Adding symbolic information to picture models: definitions and properties, First-order logics: some characterizations and closure properties, Decision problems of object histories, HDTOL matching of computations of multitape automata, On the separability of sparse context-free languages and of bounded rational relations, An undecidable problem about rational sets and contour words of polyominoes, Effective entropies and data compression, Intersections de langages algébriques bornes, Some classes of languages in \(NC^ 1\), Syntactic operators on full semiAFLs, Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete, Tetris and decidability, Quasi-polynomials, linear Diophantine equations and semi-linear sets, The Parikh counting functions of sparse context-free languages are quasi-polynomials, Additive structure of totally positive quadratic integers, Modelling economic processes by means of formal grammars: A survey of results at the middle of 1981, Bicentres de langages algébriques, Iterators for sequence expressions, Complexity and decidability for chain code picture languages, A homomorphic characterization of recursively enumerable languages, Extended automata-like regular expressions of star degree at most (2,1), On bounded interpretations of grammar forms, Order dependency in the relational model, On the growth of linear languages, Unnamed Item, The theory of languages, Counter machines and counter languages, Context-Freeness of Word-MIX Languages, A general theory of translation, A helpful result for proving inherent ambiguity, Context-free languages and rudimentary attributes, An improved proof for a theorem of N. Chomsky, The co-word problem for the Higman-Thompson group is context-free, Petri nets, commutative context-free grammars, and basic parallel processes, Unnamed Item, Quasi-realtime languages, Unnamed Item, The theory of languages, A basic course on compiler principles, A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free, Zwei Operationen zwischen Chomsky‐Grammatiken, Unnamed Item, On differentiation functions, structure functions, and related languages of context-free grammars, Unnamed Item, Flowchart machines, Unnamed Item, A note on some systems of lindenmayer, Komplexität von Algorithmen mit Anwendung auf die Analysis, Unnamed Item, Normal form of derivations in the nonassociative and commutative lambek calculus with product, Characterizations of transductions defined by abstract families of transducers, On symmetry in strings, sequences and languages, Properties of infinite words : Recent results, Proving safety properties of infinite state systems by compilation into Presburger arithmetic, 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, On the Commutative Equivalence of Algebraic Formal Series and Languages, On the multiplicity equivalence problem for context-free grammars, Synchronizing deterministic push-down automata can be really hard, Uniform tag sequences, On the Density of Context-Free and Counter Languages, An infinite hierarchy of intersections of context-free languages, Une hiérarchie des parties rationnelles de N2, Unnamed Item, On the structure of context-sensitive grammars, Unnamed Item, Sur divers produits de séries formelles, Description of developmental languages using recurrence systems, The equality of EOL languages and codings of ol languages, Unnamed Item, Unnamed Item, Unnamed Item, On a family of acceptors for some classes of developmental languages, LINGUISTIC GEOMETRY: METHODOLOGY AND TECHNIQUES, Unnamed Item, Surjectivity of functors on grammars, Recursive generation of local adjunct languages, Prefix classes of Krom formulas, Enumerating Projections of Integer Points in Unbounded Polyhedra, Development systems with finite axiom sets, Unnamed Item, Context-free preserving functions, Bottom-up and top-down tree transformations— a comparison, Parallel OL-languages, On the power of parallel communicating grammar systems with right-linear components, Unnamed Item, Unnamed Item, Topologies on formal languages, Non-prinicipalité du cylindre des langages à compteur, Le cylindre des langages linéaires, On the Boundedness Property of Semilinear Sets, Observations about bounded languages and developmental systems, A generalization of leftmost derivations, A decidability result in algebraic language theory, Locally finite languages, On Parikh slender context-free languages, On jump-deterministic pushdown automata, Contexts on trajectories, Comparing language operations, Unnamed Item, Unnamed Item, Unnamed Item, Topological properties of omega context-free languages, Wadge hierarchy of omega context-free languages, Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals, Refining nondeterminism in context-free languages, A short note on simultaneous splitting, Unnamed Item, Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs., Automata and Labyrinths, String and graph grammar characterizations of bounded regular languages, Control sets on grammars using depth-first derivations, Every commutative quasirational language is regular, Characterizations of the decidability of some problems for regular trace languages, Invito alla teoria dei linguaggi formali, On n-algebraic power series having polynomial growths11, Semilinearity of Families of Languages, A note on undecidable properties of formal languages, Die Automatentheorie als Teilgebiet der angewandten Mathematik, A Fully Equational Proof of Parikh's Theorem, Operations preserving regular languages, Numerical P systems with migrating variables, On the Density of Context-Free and Counter Languages, On a subclass of context-free groups, The equivalence of pre-NTS grammars is decidable, Unnamed Item, An undecidable problem for countable markov chains, Loops in automata and HDTOL relations, Unnamed Item, Trace languages defined by regular string languages, Interprocedural Reachability for Flat Integer Programs, Contextual grammars vs. context-free algebras, Sur les ensembles linéaires, Extension of tabled 0L-systems and languages, On some families of languages related to developmental systems, Tree Automata for Non-linear Arithmetic, Characterizations of regular and context-free matrices, Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time, Extensional Uniformity for Boolean Circuits, Time varying finite automata, Kernels of Sub-classes of Context-Free Languages, Bond-free DNA language classes, Unnamed Item, An analytic model of anaphora resolution in algebraic linguizstics, Unnamed Item, Cyclic Permutations of Letters of Words in Languages over an Alphabet, Unnamed Item, FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME, On the structure of the counting function of sparse context-free languages., Unions of certain bounded deterministic languages, Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet, Unnamed Item, Generators of regular languages, Bracketed context-free languages, Fuzzy star functions, probabilistic automata, and their approximation by non-probabilistic automata, Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, Unnamed Item, Closures which preserve finiteness in families of languages, Some definitional suggestions for automata theory, On Families of Full Trios Containing Counter Machine Languages, Checking automata and one-way stack languages, Properties of syntax directed translations, Derivation-bounded languages, On the Formalization of Some Results of Context-Free Language Theory, Zerlegungen von Semi-Thue-Systemen, Every semilinear set is a finite union of disjoint linear sets, Über einen Automaten mit Pufferspeicherung, Pure grammars and pure languages†, Unnamed Item, Parallel program schemata, Writing pushdown acceptors, Generalized sequential machine maps, On decidability and closure properties of language classes with respect to bio-operations, PATH DECOMPOSITION AND SEMILINEARITY OF PETRI NETS, A hierarchy between context-free and context-sensitive languages, Tree acceptors and some of their applications, Zur Theorie der nichtdeterministischen und unvollständigen Automaten, Three theorems concerning principal AFLs, Descriptional Complexity of Bounded Regular Languages, The solution of a problem by Ginsburg, Error detection in formal languages, On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L, Deux applications de la représentation matricielle d'une série rationnelle non commutative. (Two applications of matrix representations of a rational non -commutative series), Time-bounded grammars and their languages, Towards a theory of data structures, LR(k) grammars and deterministic languages, A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES, On non-determinacy in simple computing devices, A characterization of semilinear sets, Moments of string and derivation lengths of stochastic context-free grammars, Finite-turn checking automata, AFL with the semilinear property, Classification of noncounting events, Les 1-convexes du monoide commutatif N\(^n\), Absolutely parallel grammars and two-way finite-state transducers, Enumeration des graphes planaires à l'aide des séries formelles en variables non commutatives, Direct proofs of the undecidability of the equivalence problem for sentential forms of linear context-free grammars and the equivalence problem for OL systems, On the extension of Gladkij's theorem and the hierarchies of languages, Free and almost-free subsemigroups of a free semigroup, LR-regular grammars - an extension of LR(k) grammars, Some regular state sets in the system of one-dimensional iterative automata, A logic for document spanners, Generation, recognition and parsing of context-free languages by means of recursive graphs, ON PARTITIONS SEPARATING WORDS, Tape-reversal bounded Turing machine computations, Strict deterministic grammars, On sentential forms of context-free grammars, The equivalence problem for deterministic TOL-systems is undecidable, Sur une propriété d'itération des langages algébriques déterministes, Semi-discrete context-free languages†, Unnamed Item, GROUPS WITH INDEXED CO-WORD PROBLEM, On families of full trios containing counter machine languages, Unnamed Item, On symport/antiport P systems with a small number of objects, Decidability of trajectory-based equations, Decidable first-order transition logics for PA-processes, Two-way counter machines and finite-state transducers†, On reducing the number of states in a PDA, Characterization and complexity results on jumping finite automata
