scientific article

Publication date: 1979

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

rational functions cones context-free languages families of languages rational transductions iterative pairs classification of the subfamilies of context-free sets

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (only showing first 100 items - show all)

Using finite transducers for describing and synthesising structural time-series constraints ⋮ Reachability problems on reliable and lossy queue automata ⋮ Recognizable subsets of the two letter plactic monoid ⋮ Decision problems for word-hyperbolic semigroups ⋮ Prognosis of \(\omega\)-languages for the diagnosis of *-languages: a topological perspective ⋮ Approximation of fuzzy context-free grammars ⋮ Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable ⋮ A Kleene characterization of computability ⋮ Notions of hyperbolicity in monoids. ⋮ Termination proofs for string rewriting systems via inverse match-bounds ⋮ On regular realizability problems for context-free languages ⋮ Representation and uniformization of algebraic transductions ⋮ On the computation of quotients and factors of regular languages ⋮ Iterative and recursive matrix theories ⋮ Families of languages defined by ciliate bio-operations ⋮ Sur les générateurs algébriques et linéaires ⋮ On the rational subset problem for groups. ⋮ Fixed points of endomorphisms over special confluent rewriting systems. ⋮ A characterization of (regular) circular languages generated by monotone complete splicing systems ⋮ Kadanoff sand pile model. Avalanche structure and wave shape ⋮ Closure properties and complexity of rational sets of regular languages ⋮ Subsequential transducers: a coalgebraic perspective ⋮ Translating regular expression matching into transducers ⋮ Synchronizing relations on words ⋮ Tilings and submonoids of metabelian groups. ⋮ Look-ahead removal for total deterministic top-down tree transducers ⋮ Sur les facteurs des suites de Sturm. (On the factors of the Sturmian sequences.) ⋮ Boundary graph grammars with dynamic edge relabeling ⋮ Some decision problems about controlled rewriting systems ⋮ Probabilistic grammars and languages ⋮ On CD-systems of stateless deterministic R-automata with window size one ⋮ Unique decipherability in the monoid of languages: an application of rational relations ⋮ A standard correspondence on epicentral words ⋮ New techniques for proving the decidability of equivalence problem ⋮ A characterisation of deterministic context-free languages by means of right-congruences ⋮ Cyclic rational transductions and polynomials of rational functions ⋮ Distribution and synchronized automata ⋮ Easy multiplications. II: Extensions of rational semigroups ⋮ Closures of regular languages for profinite topologies. ⋮ Fixed points of endomorphisms of trace monoids. ⋮ Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids. ⋮ Finiteness results for subgroups of finite extensions. ⋮ Restarting transducers, regular languages, and rational relations ⋮ Language-theoretic problems in certain matrix monoids ⋮ A note on the commutative closure of star-free languages ⋮ Representations and complete semiring morphisms ⋮ Varieties and rational functions ⋮ The submonoid and rational subset membership problems for graph groups. ⋮ Synchronization ⋮ \(\mathbb{N}\)-rationality of zeta functions ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ Synchronized rational relations of finite and infinite words ⋮ On bounded rational trace languages ⋮ An optimal pre-determinization algorithm for weighted transducers ⋮ Well quasi-orders and context-free grammars ⋮ Deleting string rewriting systems preserve regularity ⋮ Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton ⋮ Equational tree transformations ⋮ Adding symbolic information to picture models: definitions and properties ⋮ Height reducing problem on algebraic integers ⋮ On suffix extensions in suffix trees ⋮ On the complexity of some extended word problems defined by cancellation rules ⋮ Expansions, free inverse semigroups, and Schützenberger product ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ Finite state complexity ⋮ On the complexity of computing the profinite closure of a rational language ⋮ La reconnaissance des facteurs d'un mot dans un texte ⋮ HDTOL matching of computations of multitape automata ⋮ Inverse subsemigroups of finite index in finitely generated inverse semigroups ⋮ On the separability of sparse context-free languages and of bounded rational relations ⋮ Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. ⋮ Semi-synchronous transductions ⋮ Infinite periodic points of endomorphisms over special confluent rewriting systems ⋮ Small overlap monoids. II: Automatic structures and normal forms. ⋮ Nivat's processing systems: decision problems related to protection and synchronization ⋮ A characterization of regular circular languages generated by marked splicing systems ⋮ The Parikh counting functions of sparse context-free languages are quasi-polynomials ⋮ Extended multi bottom-up tree transducers ⋮ Automatic presentations for semigroups. ⋮ Rational subsets of polycyclic monoids and valence automata ⋮ The class of HDT0L sequences is closed with respect to rational functions ⋮ Systems of equations over a free monoid and Ehrenfeucht's conjecture ⋮ An algebraic characterization of some principal regulated rational cones ⋮ It is decidable whether a regular language is pure context-free ⋮ Infinite linear systems and one counter languages ⋮ Bicentres de langages algébriques ⋮ Cyclic derivation of noncommutative algebraic power series ⋮ An application of the matrix representation of transductions ⋮ Linear indexed languages ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ Hierarchies of hyper-AFLs ⋮ Partial commutations and faithful rational transductions ⋮ Commutative one-counter languages are regular ⋮ A homomorphic characterization of recursively enumerable languages ⋮ The equivalence problem of multitape finite automata ⋮ Limitedness theorem on finite automata with distance functions: An algebraic proof ⋮ Computation theoretic aspects of cellular automata ⋮ Extended automata-like regular expressions of star degree at most (2,1) ⋮ On the power of synchronization in parallel computations

This page was built for publication: