scientific article

Publication date: 1986

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

power series transition matrix context-free languages regular languages pushdown automata abstract families of languages behavior of an automaton linear algebraic approach to automata and language theory

Mathematics Subject Classification ID

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

Related Items

Some consequences of a Fatou property of the tropical semiring, Context-free languages and associative algebras with algebraic Hilbert series, Language equations over a one-letter alphabet with union, concatenation and star: A complete solution, On language equations with invertible operations, Analytic models and ambiguity of context-free languages, On syntactic nuclei of rational languages, Weighted automata and weighted logics with discounting, Definable transductions and weighted logics for texts, On the context-freeness of the set of words containing overlaps, Chebyshev type inequalities for pseudo-integrals, On flowchart theories. II: The nondeterministic case, Subdirectly irreducible commutative multiplicatively idempotent semirings, Subword conditions and subword histories, Matrix systems and principal cones of algebraic power series, Skew and infinitary formal power series, Weighted tree automata and weighted logics, A unified framework for disambiguating finite transductions, Shuffle on trajectories: Syntactic constraints, Free inductive $K$-semialgebras, Computing abstract decorations of parse forests using dynamic programming and algebraic power series, Rigorous approximated determinization of weighted automata, Weighted finite automata over hemirings, On distributed catenation, On Lindenmayerian algebraic power series, On Lindenmayerian algebraic sequences, The equational logic of fixed points, Watson-Crick D0L systems: The power of one transition, On images of D0L and DT0L power series., Decidability results for Watson-Crick D0L systems with nonregular triggers., On transformations of formal power series., Varieties of recognizable tree series over fields, A linear ordering of a multi-parameter universe is usually nonsense, A Kleene-Schützenberger theorem for weighted timed automata, Finite automata theory with membership values in lattices, Parallel complexity of the regular code problem, A note on terminal balancing of algebraic systems, Generalized path-finding algorithms on semirings and the fuzzy shortest path problem., Derivatives of rational expressions and related theorems., Finite $L$-fuzzy machines., Products of matrices and recursively enumerable sets, Context-free pairs of groups. II: Cuts, tree sets, and random walks, Algebraic neighbourhood logic, Intuitionistic fuzzy left $k$-ideals of semirings., Equivalence, reduction and minimization of finite automata over semirings, $(\alpha ,\beta )$-intuitionistic fuzzy ideals of hemirings, On generalized zeta functions of formal languages and series, On the partially commutative shuffle product, Generalized semigroup semirings which are zero-divisor-free or multiplicatively left-cancellative, Representations and complete semiring morphisms, Weighted monadic Datalog, Valuations of languages, with applications to fractal geometry, Multi-weighted automata and MSO logic, Kernel methods for learning languages, General coupled semirings of residuated lattices, Nivat's theorem for pushdown transducers, Multiplicities: A deterministic view of nondeterminism, On transductions of formal power series over complete semirings, On limits in complete semirings, On stochastic pseudo-integrals with applications, Weighted automata and logics for infinite nested words, The variety of Boolean semirings, Subword histories and associated matrices, Characterizations of hemirings in terms of cubic $h$-ideals, Coupled right orthosemirings induced by orthomodular lattices, The operation $\uparrow$ on formal power series, Models of a $K$-rational identity system, Pseudo-fractional integral inequality of Chebyshev type, Weighted automata with discounting, The dual geometry of Boolean semirings, Hölder and Minkowski type inequalities for pseudo-integral, An optimal pre-determinization algorithm for weighted transducers, Branching automata with costs -- a way of reflecting parallelism in costs, Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton, Full ordering in the Shorrocks mobility sense of the semiring of monotone doubly stochastic matrices, Undecidability in matrices over Laurent polynomials., Bilinear system interconnections and generating series of weighted Petri nets, Synchronous Kleene algebra, Spectrum of prime $L$-fuzzy $h$-ideals of a hemiring., Characterizations of hemirings by their $h$-ideals., Fuzzy relation equations and reduction of fuzzy automata, Determinization of weighted finite automata over strong bimonoids, Pushdown dimension, Inequality of finite behaviors of rational weight finite automata is in R, A note on commutative multivariate rational series, On algebraic generalized zeta functions of formal power series, Characterizations of recognizable picture series, On rational series and rational languages, Weighted automata and multi-valued logics over arbitrary bounded lattices, Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring, Quantum automata and quantum grammars, Minimizing deterministic weighted tree automata, Different interpretations of triangular norms and related operations, The finite basis problem for endomorphism semirings of finite semilattices with zero., Decomposable measures and nonlinear equations, On certain closure operators defined by families of semiring morphisms, Orderings on semirings, A context-free language decision problem, Scattered deletion and commutativity, Fuzzy semirings, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, The equivalence problem for DF0L languages and power series., Equational theories of tropical semirings, On a variety of commutative multiplicatively idempotent semirings, On the varieties of ai-semirings satisfying ${x^{3}\approx x}$, Subword histories and Parikh matrices, Matrix and matricial iteration theories. I, Matrix and matricial iteration theories. II, Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids, Weighted automata and weighted logics, The variety of commutative additively and multiplicatively idempotent semirings, Infinite fuzzy computations, Inductive semimodules and the vector modules over them., Computational aspects of sturdy and flimsy numbers, Characterizations of two kinds of hemirings based on probability spaces, On pseudo-fractional integral inequalities related to Hermite-Hadamard type, Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy, New computational techniques for solving nonlinear problems using $g$-fractional differential operator, The spectra of irreducible matrices over completed idempotent semifields, On the complexity of the cogrowth sequence, Generalized expectation with general kernels on g-semirings and its applications, Discrete Watson-Crick dynamical systems, Weighted automata and weighted MSO logics for average and long-time behaviors, Noncommutative algebras, context-free grammars and algebraic Hilbert series, Minkowski type inequality for fuzzy and pseudo-integrals, Weighted simple reset pushdown automata, Weighted iterated linear control, Recognizable series on graphs and hypergraphs, On pseudo-Mittag-Leffler functions and applications, Weighted picture automata and weighted logics, Discrete bipolar pseudo-integrals, Fuzzy graphs modelling for hazmat telegeomonitoring, Generalization bounds for learning weighted automata, Commutative basic algebras and coupled near semirings, Bisimulations for weighted automata over an additively idempotent semiring, The Coxeter relations and KP map for non-commuting symbols, On $*$-$\lambda$-semirings., On injectivity of quantum finite automata, On some varieties of ai-semirings satisfying $x^{p+1} \approx x$, Quasi-universal $k$-regular sequences, Existence and uniqueness of global solution for a Cauchy problem and $g$-variational calculus, Language equivalence of probabilistic pushdown automata, The freeness problem over matrix semigroups and bounded languages, A unifying approach to algebraic systems over semirings, Refinements of Hölder's and Minkowski's type inequalities for $\sigma$-$\oplus$-measures and pseudo-expectation, Pseudo-exponential distribution and its statistical applications in econophysics, Picture deformation, Generalization of the Stolarsky type inequality for pseudo-integrals, Bisimulation relations for weighted automata, Connections between subwords and certain matrix mappings, Derivatives of rational expressions with multiplicity, Fuzzy regular languages over finite and infinite words, Generalization of the jensen inequality for pseudo-integral, Weighted path queries on semistructured databases, Generalized real analysis and its applications, Some properties of pseudo-fractional operators, On the Hurwitz product of formal power series and automata, Stochastic $g$-fractional integrals and their bounds for convex stochastic processes, Freeness properties of weighted and probabilistic automata over bounded languages, Weighted automata with storage, On the complexity of reasoning in Kleene algebra, Model checking of linear-time properties in multi-valued systems, Independence of certain quantities indicating subword occurrences, Jensen type inequality for the bipolar pseudo-integrals, A representation of residuated lattices satisfying the double negation law, Nonlinear integrals and Hadamard-type inequalities, Finite sequentiality of unambiguous max-plus tree automata, $\psi$-Mittag-Leffler pseudo-fractional operators, On the sentence valuation in a semiring, Generalized Minkowski type inequality for pseudo-integral, Principal abstract families of weighted tree languages, Weighted operator precedence languages, Bisimulation of automata, On Hadamard square roots of unity, On a Caputo-type fractional derivative respect to another function using a generator by pseudo-operations, Wirtinger integral inequalities for pseudo-integrals and pseudo-additive measure, Automata and rational expressions, Weighted automata, Enumerating regular expressions and their languages, Equational theories for automata, On D0L power series, Transformation of the pseudo-integral and related convergence theorems, Generalizations of the Steffensen integral inequality for pseudo-integrals, A refinement of the Jensen type inequality for the pseudo-integral, Entropy of generating series for nonlinear input-output systems and their interconnections, Language-theoretic aspects of DNA complementarity, The equality problem for Parikh simple algebraic power series., Automata, Boolean matrices, and ultimate periodicity., The Kleene-Schützenberger theorem for formal power series in partially commuting variables., On equations for union-free regular languages, Pushdown tree automata, algebraic tree systems, and algebraic tree series, Computing a context-free grammar-generating series, Context-free series on trees, Pseudo-cumulative distribution function with applications, On $f$-divergence for $\sigma $-$\oplus $-measures, Pseudo-analysis and its application in railway routing, Uni-transitional Watson-Crick D0L systems, Pseudo-$L^p$ space and convergence, Characterizing weighted MSO for trees by branching transitive closure logics, The presence of a zero in an integer linear recurrent sequence is NP-hard to decide, A disambiguation algorithm for weighted automata, Crisp-determinization of weighted tree automata over strong bimonoids, Self-avoiding walks and multiple context-free languages, Distributed catenation and chomsky hierarchy, Contextual grammars with distributed catenation and shuffle, Tropical Time Series, Iterated-Sums Signatures, and Quasisymmetric Functions, Automata and languages generalized to $\omega$-continuous semirings, Factor and Subsequence Kernels and Signatures of Rational Languages, Unnamed Item, Rational and Recognisable Power Series, Weighted Automata and Weighted Logics, Lindenmayer Systems, Unnamed Item, Unnamed Item, On recognizable and rational formal power series in partially commuting variables, Convolution and concurrency, On Power Series over a Graded Monoid, Temporal Specifications with Accumulative Values, Unification properties of commutative theories: A categorical treatment, Greibach normal form for $\omega$-algebraic systems and weighted simple $\omega$-pushdown automata, On quotients of formal power series, Learning Weighted Automata, Why We Need Semirings in Automata Theory (Extended Abstract), On the Disambiguation of Weighted Automata, Characterizing regular languages with polynomial densities, Knowledge and Games in Modal Semirings, Hölder and Minkowski type inequalities for pseudo-fractional integral, Cogrowth series for free products of finite groups, Decidability Boundaries for the Finite-Image Property of Weighted Finite Automata, OpenFst: A General and Efficient Weighted Finite-State Transducer Library, Weighted Automata and Weighted Logics with Discounting, Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats, The Triple-Pair Construction for Weighted ω-Pushdown Automata, On 2-absorbing ideals of commutative semirings, Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata, A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices, Program correctness and matricial iteration theories, Linear preserver of $n\times1$ Ferrers vectors, An iteration property of Lindenmayerian power series, On the multiplicity equivalence problem for context-free grammars, On (left) partial shuffle, Pumping Lemmata for Recognizable Weighted Languages over Artinian Semirings, Weighted Logics for Nested Words and Algebraic Formal Power Series, Placement Inference for a Client-Server Calculus, Generalizations of Some Inequalities for Sugino Integrals, Unnamed Item, A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata, Unnamed Item, Unnamed Item, Hermite–Hadamard’s inequality for pseudo-fractional integral operators, Unnamed Item, Unnamed Item, Birkhoff center of c-semiring, Minimizing Deterministic Weighted Tree Automata, Valuations and unambiguity of languages, with applications to fractal geometry, The algebraic equivalent of AFL theory, Solving nonlinear equations by non-additive measures, On Parikh slender context-free languages, A Finite Axiomatization of Nondeterministic Regular Expressions, Unnamed Item, Antimirov and Mosses’s Rewrite System Revisited, Tree-Series-to-Tree-Series Transformations, 3-Way Composition of Weighted Finite-State Transducers, Unnamed Item, Direct and dual laws for automata with multiplicities, Model checking for a class of weighted automata, A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic, Lattice Automata, Unnamed Item, A Kleene-Schützenberger Theorem for Weighted Timed Automata, Large-Scale Training of SVMs with Automata Kernels, Unnamed Item, Hölder type integral inequalities with different pseudo-operations, Weighted versus Probabilistic Logics, A Weighted μ-Calculus on Words, The Parikh Property for Weighted Context-Free Grammars, Acceptance Ambiguity for Quantum Automata, Partial Conway and Iteration Semiring-Semimodule Pairs, Quantum Automata Theory – A Review, Study on Some Integral Inequalities for Pseudo-Integrals, Eversible and reversible semigroups and semirings, Structure of Birkhoff center of c-semirings, A representation of basic algebras by coupled right near semirings, (f, g)-derivation of ordered Γ-semirings, On the Rademacher Complexity of Weighted Automata, Weighted Operator Precedence Languages, Varieties of Burnside ai-semirings satisfying xn ≈ x, A common algebraic description for probabilistic and quantum computations, $*$-$\mu$-semirings and $*$-$\lambda$-semirings, On morphically generated formal power series, Unnamed Item, Some new semiring structures, A Fully Equational Proof of Parikh's Theorem