scientific article

Publication date: 4 November 2009

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

finite automata formal languages morphisms free monoids formal power series weighted automata functional transducers

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Zeno, Hercules, and the Hydra, Bidirectional Runtime Enforcement of First-Order Branching-Time Properties, Crisp-determinization of weighted tree automata over strong bimonoids, Morphisms and Minimisation of Weighted Automata, Semantic Foundations for Deterministic Dataflow and Stream Processing, On the Balancedness of Tree-to-Word Transducers, On rationally controlled one-rule insertion systems, Consensus Game Acceptors, Multi-sequential Word Relations, Tropical Time Series, Iterated-Sums Signatures, and Quasisymmetric Functions, Rational base number systems forp-adic numbers, Factor and Subsequence Kernels and Signatures of Rational Languages, Ultimate periodicity problem for linear numeration systems, Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory, Games with Symmetric Incomplete Information and Asymmetric Computational Resources, Unnamed Item, Birecurrent sets, On Multiplicative Independent Bases for Canonical Number Systems in Cyclotomic Number Fields, From Ambiguous Regular Expressions to Deterministic Parsing Automata, Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata, On the Semantics of Regular Expression Parsing in the Wild, Polynomially ambiguous unary weighted automata over fields, The palindromization map, Modelling Uncertainty in Architectures of Parametric Component-Based Systems, Decidability Boundaries for the Finite-Image Property of Weighted Finite Automata, D-finite multivariate series with arithmetic restrictions on their coefficients, On first-order runtime enforcement of branching-time properties, Bideterministic weighted automata, When variable-length codes meet the field of error detection, Zero-Avoiding Transducers, Length Separable Relations, and the Rational Asymmetric Partition Problem, Decidability of regular language genus computation, Representing regular languages of infinite words using mod 2 multiplicity automata, A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices, The genus of regular languages, Bideterministic weighted automata, Abelian Invertible Automata, Unnamed Item, Topologies for error-detecting variable-length codes, A Fibonacci analogue of the two’s complement numeration system, Synthesizing Computable Functions from Rational Specifications Over Infinite Words, Recognizability in residuated lattices, Unnamed Item, Input- or output-unary sweeping transducers are weaker than their 2-way counterparts, Two-way representations and weighted automata, Eraser morphisms and membership problem in groups and monoids, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Degree of Sequentiality of Weighted Automata, Unnamed Item, Unnamed Item, From Combinatorial Games to Shape-Symmetric Morphisms, Yet Another Characterization of the Pisot Substitution Conjecture, Injective envelopes of transition systems and Ferrers languages, On Hadamard Series and Rotating Q-Automata, Calculational design of a regular model checker by abstract interpretation, Consensus Game Acceptors and Iterated Transductions, Multi-Sequential Word Relations, On the length of fully commutative elements, Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems, Theme and Variations on the Concatenation Product, Algebra-coalgebra duality in brzozowski's minimization algorithm, A list of applications of Stallings automata, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata, Rational Selecting Relations and Selectors, On Average Behaviour of Regular Expressions in Strong Star Normal Form, Partial derivatives of regular expressions over alphabet-invariant and user-defined labels, Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization, Unnamed Item, Graph Logics with Rational Relations, From Hadamard expressions to weighted rotating automata and back, Unnamed Item, Unnamed Item, Complementation of Branching Automata for Scattered and Countable Series-Parallel Posets, Position Automaton Construction for Regular Expressions with Intersection, Both Ways Rational Functions, Weighted Symbolic Automata with Data Storage, Computing Maximal Kleene Closures That Are Embeddable in a Given Constrained DNA Language, A Formal Framework for Complex Event Processing, A congruence-based perspective on automata minimization algorithms, Rational Transformations and a Kleene Theorem for Power Series over Rational Monoids, Implementation of Code Properties via Transducers, Roots and Powers in Regular Languages: Recognizing Nonregular Properties by Finite Automata, Languages, Decidability, and Complexity, The Shortest Identities for Max-Plus Automata with Two States., Unambiguity in Automata Theory, Robust Stability of Input-Output Systems with Initial Conditions, Unnamed Item, Quantifiers on languages and codensity monads, Regular Expressions and Transducers Over Alphabet-Invariant and User-Defined Labels, A New Hierarchy for Automaton Semigroups, Semilinearity of Families of Languages, Using finite transducers for describing and synthesising structural time-series constraints, Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits, Topological abstraction of higher-dimensional automata, The universal fuzzy automaton, Brzozowski type determinization for fuzzy automata, Automata, reduced words and Garside shadows in Coxeter groups., Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids, Crystal monoids \& crystal bases: rewriting systems and biautomatic structures for plactic monoids of types \(A_{n}\), \(B_{n}\), \(C_{n}\), \(D_{n}\), and \(G_{2}\), Regular model checking with regular relations, On fixed points of rational transductions, On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups, Rational digit systems over finite fields and Christol's theorem, Preservation of normality by unambiguous transducers, Manipulation of regular expressions using derivatives: an overview, Purity results for some arithmetically defined measures, A simple method for building bimachines from functional finite-state transducers, Rational elements of summation semirings, A contribution to the determinization of max-plus automata, The \(\kappa\)-word problem over \(\mathsf{DRH}\), Free inductive \(K\)-semialgebras, Sofic tree-shifts, Expressiveness and static analysis of extended conjunctive regular path queries, On quotients of formal power series, Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated, Bijections between Łukasiewicz walks and generalized tandem walks, Integrability and geometry of the Wynn recurrence, Quasi-automatic semigroups, On counting functions and slenderness of languages, Rationality for subclasses of 321-avoiding permutations, On the rational subsets of the monogenic free inverse monoid, Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences, Free iterative and iteration \(K\)-semialgebras, Finite-state independence and normal sequences, Recognizable series on graphs and hypergraphs, On the membership problem for finite automata over symmetric groups, Primitive matrices over polynomial semirings, Translating regular expression matching into transducers, The carry propagation of the successor function, Bisimulations for fuzzy automata, On the supports of recognizable series over a field and a single letter alphabet, Nondeterministic automata: equivalence, bisimulations, and uniform relations, Synchronizing relations on words, Location automata for synchronised shuffle expressions, Transducer descriptions of DNA code properties and undecidability of antimorphic problems, On the average complexity of partial derivative transducers, Efficient algorithms for computing the inner edit distance of a regular language via transducers, Algebraic state space approach to model and control combined automata, Adding pebbles to weighted automata: easy specification \& efficient evaluation, Bisimulations for weighted automata over an additively idempotent semiring, Set systems: order types, continuous nondeterministic deformations, and quasi-orders, Redundancy of minimal weight expansions in Pisot bases, Weak morphisms of higher dimensional automata, Finiteness results for subgroups of finite extensions., Normality and automata, Language-theoretic problems in certain matrix monoids, Copyless cost-register automata: structure, expressiveness, and closure properties, The dual equivalence of equations and coequations for automata, Coalgebraic minimization of automata by initiality and finality, Ordering sequences by permutation transducers, Deciding game invariance, An Hadamard operation on rational relations, Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity, Colored operads, series on colored operads, and combinatorial generating systems, A unifying approach to algebraic systems over semirings, Tree-shifts of finite type, Formalizing a fragment of combinatorics on words, Robustness of Pisot-regular sequences, Space-efficient bimachine construction based on the equalizer accumulation principle, Rational relations having a rational trace on each finite intersection of rational relations, A mesh of automata, Weighted automata with storage, Finite-state independence, A geometric and combinatorial exploration of Hochschild lattices, Hopf algebra structure of generalized quasi-symmetric functions in partially commutative variables, Conditions for the existence of maximal factorizations, Noncommutative rational Pólya series, Maximal bifix decoding, Minimal automaton for multiplying and translating the Thue-Morse set, On deterministic weighted automata, Finite sequentiality of unambiguous max-plus tree automata, Determinisability of unary weighted automata over the rational numbers, Generic results for concatenation hierarchies, Preservation of normality by transducers, Principal abstract families of weighted tree languages, On finitely generated submonoids of virtually free groups, Canonization of max-min fuzzy automata, Geometrically closed positive varieties of languages, Diameter and stationary distribution of random \(r\)-out digraphs, On some decidability questions concerning supports of rational series, Finite ambiguity and finite sequentiality in weighted automata over fields, A robust class of linear recurrence sequences, Theoretical and implementational aspects of the formal language server (LaSer), Rational subsets and submonoids of wreath products., A formalisation of the Myhill-Nerode theorem based on regular expressions, Computing maximal Kleene closures that are embeddable in a given subword-closed language, Characterizing weighted MSO for trees by branching transitive closure logics, On bidirectional runtime enforcement, Algorithmic aspects of decomposition and equivalence of finite-valued transducers, On the semantics of regular expression parsing in the wild, On the hierarchy of generalizations of one-unambiguous regular languages