Publication:3644388

Publication date: 4 November 2009

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

Mathematics Subject Classification ID

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

68Q45: Formal languages and automata

68Q70: Algebraic theory of languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Games with Symmetric Incomplete Information and Asymmetric Computational Resources, Birecurrent sets, On Multiplicative Independent Bases for Canonical Number Systems in Cyclotomic Number Fields, The genus of regular languages, Consensus Game Acceptors and Iterated Transductions, Multi-Sequential Word Relations, On the length of fully commutative elements, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Roots and Powers in Regular Languages: Recognizing Nonregular Properties by Finite Automata, Unnamed Item, Quantifiers on languages and codensity monads, Ultimate periodicity problem for linear numeration systems, Unnamed Item, Decidability of regular language genus computation, Abelian Invertible Automata, Eraser morphisms and membership problem in groups and monoids, From Combinatorial Games to Shape-Symmetric Morphisms, Yet Another Characterization of the Pisot Substitution Conjecture, On Average Behaviour of Regular Expressions in Strong Star Normal Form, Graph Logics with Rational Relations, Unnamed Item, Unnamed Item, Zeno, Hercules, and the Hydra, Algebra-coalgebra duality in brzozowski's minimization algorithm, Languages, Decidability, and Complexity, Unambiguity in Automata Theory, Robust Stability of Input-Output Systems with Initial Conditions, Calculational design of a regular model checker by abstract interpretation, Partial derivatives of regular expressions over alphabet-invariant and user-defined labels, From Hadamard expressions to weighted rotating automata and back, Regular Expressions and Transducers Over Alphabet-Invariant and User-Defined Labels, A New Hierarchy for Automaton Semigroups, Semilinearity of Families of Languages, Two-way representations and weighted automata, Degree of Sequentiality of Weighted Automata, Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems, Theme and Variations on the Concatenation Product, Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization, Computing Maximal Kleene Closures That Are Embeddable in a Given Constrained DNA Language, Rational Transformations and a Kleene Theorem for Power Series over Rational Monoids, Unnamed Item, Injective envelopes of transition systems and Ferrers languages, Consensus Game Acceptors, Multi-sequential Word Relations, Computing maximal Kleene closures that are embeddable in a given subword-closed language, Algorithmic aspects of decomposition and equivalence of finite-valued transducers, 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., 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, Free inductive \(K\)-semialgebras, Sofic tree-shifts, Expressiveness and static analysis of extended conjunctive regular path queries, Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated, Free iterative and iteration \(K\)-semialgebras, Primitive matrices over polynomial semirings, Translating regular expression matching into transducers, Bisimulations for fuzzy automata, Finiteness results for subgroups of finite extensions., Normality and automata, Language-theoretic problems in certain matrix monoids, The dual equivalence of equations and coequations for automata, Ordering sequences by permutation transducers, Deciding game invariance, An Hadamard operation on rational relations, Set systems: order types, continuous nondeterministic deformations, and quasi-orders, Redundancy of minimal weight expansions in Pisot bases, Rational relations having a rational trace on each finite intersection of rational relations, Diameter and stationary distribution of random \(r\)-out digraphs, Nondeterministic automata: equivalence, bisimulations, and uniform relations, Synchronizing relations on words, 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}\), On fixed points of rational transductions, The \(\kappa\)-word problem over \(\mathsf{DRH}\), Transducer descriptions of DNA code properties and undecidability of antimorphic problems, Efficient algorithms for computing the inner edit distance of a regular language via transducers, Algebraic state space approach to model and control combined automata, Copyless cost-register automata: structure, expressiveness, and closure properties, Coalgebraic minimization of automata by initiality and finality, Tree-shifts of finite type, Finite-state independence, On deterministic weighted automata, Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences, On the supports of recognizable series over a field and a single letter alphabet, 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, Formalizing a fragment of combinatorics on words, Robustness of Pisot-regular sequences, 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, Minimal automaton for multiplying and translating the Thue-Morse set, Finite sequentiality of unambiguous max-plus tree automata, Determinisability of unary weighted automata over the rational numbers, Preservation of normality by transducers, Principal abstract families of weighted tree languages, On bidirectional runtime enforcement, Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids, Regular model checking with regular relations, A contribution to the determinization of max-plus automata, Bijections between Łukasiewicz walks and generalized tandem walks, The carry propagation of the successor function, Space-efficient bimachine construction based on the equalizer accumulation principle, A mesh of automata, Weighted automata with storage, Generic results for concatenation hierarchies, On finitely generated submonoids of virtually free groups, Canonization of max-min fuzzy automata, Rational subsets and submonoids of wreath products., A formalisation of the Myhill-Nerode theorem based on regular expressions, Characterizing weighted MSO for trees by branching transitive closure logics, On the semantics of regular expression parsing in the wild, On the hierarchy of generalizations of one-unambiguous regular languages, A simple method for building bimachines from functional finite-state transducers, Quasi-automatic semigroups, On counting functions and slenderness of languages, Rationality for subclasses of 321-avoiding permutations, Finite-state independence and normal sequences, Recognizable series on graphs and hypergraphs, Adding pebbles to weighted automata: easy specification \& efficient evaluation, Bisimulations for weighted automata over an additively idempotent semiring, Weak morphisms of higher dimensional automata, Maximal bifix decoding, Rational elements of summation semirings, On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata, Rational Selecting Relations and Selectors, 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, Implementation of Code Properties via Transducers, Rational base number systems forp-adic numbers, Factor and Subsequence Kernels and Signatures of Rational Languages, Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory, 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, Input- or output-unary sweeping transducers are weaker than their 2-way counterparts