scientific article; zbMATH DE number 3497806

zbMath0317.94045MaRDI QIDQ4079524

Samuel Eilenberg

Publication date: 1974

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Automata and formal grammars in connection with logical questions (03D05) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items

Repetition-free words, Rational languages and the Burnside problem, Truncations of infinite matrices and algebraic series associated with some CF grammars, On coordinated selective substitutions: Towards a unified theory of grammars and machines, Systèmes codés. (Coded systems), Infinite-word languages and continuous mappings, Petri nets with individual tokens, Addition molle et fonctions p-locales, A simple proof of the Skolem-Mahler-Lech theorem, About fair asynchrony, Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht, A note on the equivalence problem of rational formal power series, On equality of multiplicity sets of regular languages, The complementation problem for Büchi automata with applications to temporal logic, Rational equivalence relations, Finitely generated \(\omega\)-languages, Noncommutative factorization of variable-length codes, On generators of rational \(\omega\)-power languages, On regular trace languages, Le calcul rapide des mélanges de deux mots. (Fast computing of the shuffle of two words), Quasicrystal Ising chain and automata theory, Recognizing safety and liveness, On flowchart theories. II: The nondeterministic case, Easy multiplications. I: The realm of Kleene's theorem, A remark on bilinear systems and moduli spaces of instantons, Linear numeration systems of order two, Varieties of formal series on trees and Eilenberg's theorem, Iterated GSMs and CO-CFL, Expletives in languages and middle units in semigroups, Test sets for languages of infinite words, Ein Satz über die Entropie von Untermonoiden. (A theorem on the entropy of submonoids), A closure property of regular languages, Shortest path under rational constraint, A generalization of automatic sequences, La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time), Counting with rational functions, A unified framework for disambiguating finite transductions, Concatenation of inputs in a two-way automaton, Accepting conditions for automata on \(\omega\)-languages, A maxmin problem on finite automata, Construction of a family of finite maximal codes, Sur les entiers qui s'écrivent simplement en différentes bases. (On integers simply represented in different bases), Construction d'une famille de codes associés à certains groupes finis. (Construction of a family of codes associated to certain finite groups), Rational probability measures, Concurrent transition systems, On a conjecture of Rhodes, A necessary condition for the rationality of the zeta function of a regular language, Applications of the theory of automata in enumeration, Shuffle-compatible total orders, Every finitely generated submonoid of a free monoid has a finite Malcev's presentation, Sur les automates qui reconnaissent une famille de langages. (On the automata which accept a family of languages), Deterministic synchronization of automata with bounded delay, Shuffle on trajectories: Syntactic constraints, Le degré minimal du groupe d'un code biprefixe fini, Sur le théorème du defaut, On some properties of very pure codes, La représentation ergodique d'un automate fini, A cyclic derivative in noncommutative algebra, Partially additive categories and flow-diagram semantics, One-way weak-stack-counter automata, Rational bijection of rational sets, Recognizable sets and power sets of finite semigroups, On finite \(\mathcal J\)-trivial monoids, Machines in a category, A complete axiom system for rational sets with multiplicity, Une topologie du monoide libre, Combinatorial aspects of continued fractions, Minimal complete sets of words, Regular semigroups with D=R as syntactic monoids of prefix codes, Foundations of system theory: The Hankel matrix, Operatorenkalkül über freien Monoiden I: Strukturen, On generalized language equations, Remarks on the pole-shifting problem over rings, Sur les séries associees à certains systèmes de Lindenmayer, Enumeration d'arbres et formules d'inversion de séries formelles, Concise description of finite languages, Adherences of languages, Decoupling of nonlinear systems, Equivalence, reduction and minimization of finite fuzzy-automata, Generalization of the Ginsburg-Rice Schuetzenberger fixed-point theorem for context-sensitive and recursive-enumerable languages, Presentations et presentations simplifiables d'un monoide simplifiable, On varieties of rational languages and variable-length codes, Semisimplicity of the algebra associated to a biprefix code, Properties of structure generating functions of automata and their applications for linear systems, Recognizable formal power series on trees, Binary systems all subsets of which are recognizable, A synchronization property of pure subsemigroups of a free semigroup, On infinite words obtained by iterating morphisms, Parallel language recognition in constant time by cellular automata, Langages satures et cônes decroissants. Langages et cônes bifideles, Ensembles code-compatibles et une généralisation du théorème de Sardinas-Patterson, Extended macro grammars and stack controlled machines, Towards a formal proof system for \(\omega\)-rational expressions, Automates finis et ensembles normaux. (Finite automata and normal sets), A syntactic congruence for rational \(\omega\)-languages, On infinite words obtained by selective substitution grammars, On cancellation properties of languages which are supports of rational power series, Classes of regular and context-free languages over countably infinite alphabets, Some properties of commutation in free partially commutative monoids, An algorithm to decide whether a rational subset of \({\mathbb{N}}^ k\) is recognizable, Varieties and covarieties of languages (extended abstract), Automata-theoretic semantics of idealized Algol with passive expressions, Smooth finitely computable functions are affine, or why quantum systems cause waves, Identifying all preorders on the subdistribution monad, Hyperquadratic continued fractions and automatic sequences, Noncommutative minimization algorithms, On syntactic nuclei of rational languages, On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups, Finding all solutions of equations in free groups and monoids with involution, On groups whose word problem is solved by a counter automaton., Real numbers having ultimately periodic representations in abstract numeration systems, Families of recognizable sets corresponding to certain varieties of finite monoids, On commutative DTOL systems, Sur les générateurs algébriques et linéaires, Determinization of ordinal automata, Free inductive \(K\)-semialgebras, Automata and processes on multisets of communicating objects, The tensor product of function semimodules., Weighted finite automata over hemirings, Möbius inversion formula for monoids with zero., Subsequential transducers: a coalgebraic perspective, Path sets in one-sided symbolic dynamics, Algebraic Myhill-Nerode theorems, On factors of synchronized sequences, Free iterative and iteration \(K\)-semialgebras, First order representations of Fliess models, An inner product space on irreducible and synchronizable probabilistic finite state automata, Varieties of recognizable tree series over fields, Coping with selfish on-going behaviors, On algebra of languages representable by vertex-labeled graphs, Properties and limits of recognition of sets of integers by countable automata, Automata theory based on lattice-ordered semirings, Finite automata theory with membership values in lattices, Model-theoretic complexity of automatic structures, Finite state wreath powers of transformation semigroups., Another approach to the equivalence of measure-many one-way quantum finite automata and its application, Extremal minimality conditions on automata, Partial-realization theory for linear switched systems -- a formal power series approach, Geometrically minimal realizations of Boolean controlled systems, Which security policies are enforceable by runtime monitors? A survey, Comments on the height reducing property. II, On the Fibonacci-Mandelbrot set, Stochastic adding machine and 2-dimensional Julia sets, On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\), A characterization of \(p\)-automatic sequences as columns of linear cellular automata, Budget-bounded model-checking pushdown systems, On the digits of shifted primes, On vanishing coefficients of algebraic power series over fields of positive characteristic, On the regularity of the Hankel determinant sequence of the characteristic sequence of powers of 2, Basic notions of universal algebra for language theory and graph grammars, On the vector space of the automatic reals, Local languages and the Berry-Sethi algorithm, The dual equivalence of equations and coequations for automata, A canonical automaton for one-rule length-preserving string rewrite systems, Implicit language equations: existence and uniqueness of solutions, Varieties and rational functions, Approximately satisfied properties of systems and simple language homomorphisms, Substitutions and \(\beta\) systems of numeration, Equational properties of Kleene algebras of relations with conversion, On the 2-abelian complexity of the Thue-Morse word, A decision method for Parikh slenderness of context-free languages, Multi-weighted automata and MSO logic, \(\mathbb{N}\)-rationality of zeta functions, Automaticity. IV: Sequences, sets, and diversity, Automatic maps in exotic numeration systems, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, On certain recurrent and automatic sequences in finite fields, Weighted automata and logics for infinite nested words, On the decomposition of prefix codes, Equations over finite sets of words and equivalence problems in automata theory, Synchronized rational relations of finite and infinite words, The pro-nilpotent group topology on a free group, The operation \(\uparrow\) on formal power series, The poset of infinitary traces, Error-correcting codes and phase transitions, Deciding word neighborhood with universal neighborhood automata, The dual geometry of Boolean semirings, An optimal pre-determinization algorithm for weighted transducers, Acyclic networks maximizing the printing complexity, Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton, Undecidability in matrices over Laurent polynomials., Height reducing problem on algebraic integers, Learning in the limit with lattice-structured hypothesis spaces, Prefix-primitive annihilators of languages under some operations, Model matching inclusion for input/state asynchronous sequential machines, Representing real numbers in a generalized numeration system, The set of realizations of a max-plus linear sequence is semi-polyhedral, The growth function of \(S\)-recognizable sets, La reconnaissance des facteurs d'un mot dans un texte, Presentations of inverse monoids, Automata on infinite objects and their applications to logic and programming, A remark on the representation of trace monoids, Final and sequential behaviours of M-automata, Circular Sturmian words and Hopcroft's algorithm, The computational status of physics, Constructions effectives sur les séries formelles d'arbres. (Effective constructions on formal tree series), The zig-zag power series: A two-way version of the \({}^*\) operator., Intersections de langages algébriques bornes, The solutions of two star-height problems for regular trees, Automatic congruences for diagonals of rational functions, Some consequences of a Fatou property of the tropical semiring, On some arithmetic properties of Mahler functions, Asynchronous automata versus asynchronous cellular automata, Formal languages defined by uniform substitutions, Well quasi-orders and regular languages, Representation of rational functions with prefix and suffix codings, A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring, Periodic sets of integers, Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition, Notes on equational theories of relations, Polynomial closure of group languages and open sets of the Hall topology, On the linearity of on-line computable functions, Flatwords and Post Correspondence Problem, Semi-Galois categories. II: An arithmetic analogue of Christol's theorem, Inversion of linear systems on the basis of state space realization, Slightly commutative Kleene semigroups, Polynomial closure and unambiguous product, Subspace arrangements over finite fields: Cohomological and enumerative aspects, A class of non-deterministic specifications for supervisory control, Fuzzifications of concrete categories and homomorphy degrees of mappings between universal algebras, On the automorphism group of the one-rooted binary tree, A characterization of substitutive sequences using return words, Visibly pushdown transducers, Using automata theory for characterizing the semantics of terminological cycles, Positive tree representations and applications to tree automata, On the sequentiality of the successor function, The set of minimal words of a context-free language is context-free, On projective and separable properties, Some decisional problems on rational relations, Separators in infinite words generated by morphisms., On syntactic congruences for \(\omega\)-languages, Bertrand numeration systems and recognizability, Recognizable picture languages and domino tiling, The equational logic of fixed points, Succinctness of descriptions of SBTA-languages, On the \(k\)-abelian complexity of the Cantor sequence, Ambiguity in omega context free languages, Test sets for the universal and existential closure of regular tree languages., An automaton group with undecidable order and Engel problems, Borel hierarchy and omega context free languages., On images of D0L and DT0L power series., Shape preserving top-down tree transducers., On transformations of formal power series., Generalization bounds for learning weighted automata, The ring of \(k\)-regular sequences. II., Derivatives of rational expressions and related theorems., Characterizations of fuzzy finite automata., Finite \(L\)-fuzzy machines., The Weyl group of the Cuntz algebra, On the algorithmic decidability of the second-type annihilation predicate for varieties of semigroups, Construction of fuzzy automata from fuzzy regular expressions, Injective envelope and parallel decomposition of a transition system, Succinct representations of languages by DFA with different levels of reliability, Learning local transductions is hard, Abstract state machines: a unifying view of models of computation and of system design frameworks, It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base, The structure of reflexive regular splicing languages via Schützenberger constants, Characterizations and effective computation of supremal relatively observable sublanguages, A hierarchical consistency framework for real-time supervisory control, A categorical approach to minimal realization for a fuzzy language, Weighted finite transducers in image processing, Semigroups and the self-similar structure of the flipped Tribonacci substitution, Logic, semigroups and automata on words, Morphismes unispectraux. (Unispectral morphisms), Disjunctive decomposition of languages, Fixed point languages of rational transductions, Two characterizations of rational adherences, Characterization of \(\omega\)-regular languages by monadic second-order formulas, Minimal automaton for a factorial, transitive, and rational language, Series-parallel languages and the bounded-width property, Membership problems for regular and context-free trace languages, On a possible classification of real-time constructed sequences, \(\beta\)-expansions and symbolic dynamics, m-recognizability of sets closed under certain affine functions, Codes engendrant certains systèmes sofiques. (Codes generating certain sofic systems), Minimization algorithms for sequential transducers, Automata of asynchronous behaviors, Undecidability of existential properties in picture languages, Sous-monoides et codes avec des mots infinis, Langages à un compteur, Infinite arrays and infinite computations, Asynchronous cellular automata for pomsets, Forbidden words in symbolic dynamics, An equivalence relation on \(\{ 0,1\}^*\), How to decide continuity of rational functions on infinite words, Conway's problem for three-word sets., Extensions and submonoids of automatic monoids., On the lattice of prefix codes., Squaring transducers: An efficient procedure for deciding functionality and sequentiality., On a valuation of rational subsets of \(Z^{k}\), On-line digit set conversion in real base., Regular Gröbner bases, Modelization of deterministic rational relations, Iterated relabeling tree transducers, The commutation of finite sets: A challenging problem, Words and forbidden factors, Quantum evolution of words, Numeration systems and automata, Distances between languages and reflexivity of relations, A study of behaviors, Reducing local alphabet size in recognizable picture languages, On the recognizability of fuzzy languages. II, Deciding determinism of caterpillar expressions, Weighted automata and weighted logics with discounting, A computational model for tiling recognizable two-dimensional languages, Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable, A Kleene characterization of computability, On the recognizability of fuzzy languages. I, Representation and uniformization of algebraic transductions, Obtaining shorter regular expressions from finite-state automata, The origins of combinatorics on words, On the rational subset problem for groups., Quantization causes waves: smooth finitely computable functions are affine, Codes and local constraints, Effective construction of the syntactic algebra of a recognizable series on trees, Parallel complexity of the regular code problem, Sur les codes zigzag et leur décidabilité. (Zigzag codes and their decidability), Algebraic specification of concurrent systems, f-disjunctive congruences and a generalization of monoids with length, Cyclic rational transductions and polynomials of rational functions, The three subfamilies of rational \(\omega\)-languages closed under \(\omega\)-transduction, Easy multiplications. II: Extensions of rational semigroups, X-machines and the halting problem: Building a super-turing machine, Structural cascade decomposition of stationary linear systems connected with the Kalman decomposition, On aperiodic and star-free formal power series in partially commuting variables, Schützenberger's theorem on formal power series follows from Kleene's theorem, Testing data processing-oriented systems from stream X-machine models, Weighted monadic Datalog, Generalizations of 1-deterministic regular languages, Green index and finiteness conditions for semigroups., Weighted automata with discounting, Myhill-Nerode type theory for fuzzy languages and automata, On bounded rational trace languages, On a problem of Gelfond: the sum of digits of prime numbers, \(\mathbb Z\)-rationality of a certain class of formal series, Generating series for bilinear hybrid systems, Span-reachability and observability of bilinear hybrid systems, Checking experiments for stream X-machines, Characterizations of hemirings by their \(h\)-ideals., Determinization of weighted finite automata over strong bimonoids, On a zeta function associated with automata and codes, On the separability of sparse context-free languages and of bounded rational relations, Powers of rationals modulo 1 and rational base number systems, Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al., Infinite-vertex free profinite semigroupoids and symbolic dynamics., Self-similar tiling systems, topological factors and stretching factors, Deterministic and unambiguous two-dimensional languages over one-letter alphabet, Testing a deterministic implementation against a non-controllable non-deterministic stream X-machine, About frequencies of letters in generalized automatic sequences, Characterizations of recognizable picture series, Bilimites de langages reconnaissables, A characterization of s-languages, Lattices of local two-dimensional languages, Weighted automata and multi-valued logics over arbitrary bounded lattices, Multi-letter quantum finite automata: decidability of the equivalence and minimization of states, Equational weighted tree transformations, Strongly transitive automata and the Černý conjecture, Automata theory based on complete residuated lattice-valued logic: a categorical approach, Cayley graphs as classifiers for data mining: the influence of asymmetries, An automaton-theoretic approach to the representation theory of quantum algebras, Some remarks on non-algebraic adherences, An algebraic characterization of some principal regulated rational cones, Hereditary realizations of linear neutral delay-differential systems, Real functions and numbers defined by Turing machines, Realisation locale des systèmes non linéaires, algèbres de Lie filtrees transitives et séries generatrices non commutatives, Completing biprefix codes, A propos d'une conjecture de F. Dejean sur les répétitions dans les mots, A note on \(\omega\)-regular languages, Extensions of iterative congruences of free iterative algebras, Modelling economic processes by means of formal grammars: A survey of results at the middle of 1981, On the centers of a language, Rational \(\omega\)-languages are non-ambiguous, Cyclic derivation of noncommutative algebraic power series, Power monoids and finite J-trivial monoids, An application of the matrix representation of transductions, Alternating finite automata on \(\omega\)-words, Projection lemmas for \(\omega\)-languages, Infinite arrays and controlled deterministic table 0L array systems, Bases and ambiguity of number systems, The shuffle algebra on the factors of a word is free, On conceptual completeness of syntactic-semantical systems, On formal power series defined by infinite linear systems, Biprefix codes, inverse semigroups and syntactic monoids of injective automata, Polynomials associated with the characters of SU(n), Equivalence of infinite behavior of finite automata, The inverse semigroup of a sum-ordered semiring, Characterization of \(\omega\)-regular languages by first-order formulas, Langages infinitaires et produit de mixage, Codeterministic automata on infinite words, Automates boustrophédon et mots infinis, Relations rationnelles infinitaires, The equivalence problem of multitape finite automata, On the expressive power of temporal logic for infinite words, Sequential machines realized by group representations, Closure functions and general iterates as reflectors, On finitely recognizable semigroups, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Control of discrete-event systems with partial observations using coalgebra and coinduction, On the growth of linear languages, Abstract abstract reduction, Finite state relational programs, A class of fuzzy theories, Nest sets and relativized closure properties, Decidability of Skolem matrix emptiness problem entails constructability of exact regular expression, The limited regular languages, Automatic average-case analysis of algorithms, Towards a formal description of intracellular biochemical organization, Counting monoids and rational languages, Finiteness and iteration conditions for semigroups, Equivalence, reduction and minimization of finite automata over semirings, Languages and scanners, Which Kleene semigroups are finite?, Decidability problems for unary output sequential transducers, Finitely generated bi\(\omega\)-languages, The Hausdorff-Kuratowski hierarchy of \(\omega\)-regular languages and a hierarchy of Muller automata, Generalized semigroup semirings which are zero-divisor-free or multiplicatively left-cancellative, Clocks in dataflow languages, On condition/event systems with discrete state realizations, Contractive presentations: A family of inverse monoids and semigroups with finite \({\mathcal R}\)-classes, AUTOMATE, a computing package for automata and finite semigroups, Rationality of the Möbius function of subword order, Linear numeration systems and \(\theta\)-representations, A note on renewal systems, Triangular norm-based measures and their Markov kernel representation, Fairness, distances and degrees, Nivat's theorem for pushdown transducers, Star-free trace languages, The ring of \(k\)-regular sequences, Alphabetic tree relations, On the decidability of the equivalence problem for partially commutative rational power series, Rational relations and rational series, Multiplicities: A deterministic view of nondeterminism, On transductions of formal power series over complete semirings, Rational series with coefficients in a commutative ring, On limits in complete semirings, The variety of Boolean semirings, \(\infty\)-regular temporal logic and its model checking problem, Models of a \(K\)-rational identity system, Confluent linear numeration systems, The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable, Data machines and standards, or the functional specification of information systems, \(X\)-automata on \(\omega\)-words, On the limit set of some universal cellular automata, Transductions de séries formelles, Progress in free associative algebras, The real numbers as a wreath product, Two theorems concerning recognizable \(N\)-subsets of \(\sigma^*\), Recognizable languages and finite semilattices of groups, La transitivite du groupe d'un code biprefixe fini, Positive rational sequences, Comparability graphs and a new matroid, Sur les rélations rationnelles entre monoides libres, On some questions of rationality and decidability, A decidability result for deterministic \(\omega\)-context-free languages, Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages, Analyse und Synthese von asynchronen ND-Automaten, \(\omega\)-computations on Turing machines, Remarks on commutative N-rational series, Single-valued a-transducers, On finite semigroups of matrices, On a question of S. Eilenberg, Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles, On tree transducers for partial functions, Duality and the regulator problem for linear systems over commutative rings, A combinatorial property of codes having finite synchronization delay, \(\omega\)-computations on deterministic pushdown machines, Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices, Some languages derived from abelian groups, Semirings and path spaces, Equivalence problem of non-deterministic finite automata, A new proof of two theorems about rational transductions, Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets), Transformationendarstellungen endlicher abstrakt präsentierter Halbgruppen, On the existence of minimal realizations of linear dynamical systems over Noetherian integral domains, Characterizing the regular prefix codes and right power-bounded languages, Overlap-free words and finite automata, Finitely generated sofic systems, Methods of invariant analysis for linear control systems., On number systems with finite degree of ambiguity, On recognizable sets of integers, Arithmetic and dynamical properties of the Rauzy fractal, Polygonal radix representations of complex numbers, Independent numeration systems and syndeticity, A construction on finite automata that has remained hidden, On quasi orders of words and the confluence property, Deterministic generalized automata, The semilattices of nilextensions of left groups and their varieties, Non-uniform random spanning trees on weighted graphs, A characterization of recognizable picture languages by tilings by finite sets, Maximal bifix codes, Varieties and pseudovarieties of ordered normal bands, Opacity of finite automata, Completely regular semigroups as semigroups of partial transformations, A partial result about the factorization conjecture for finite variable- length codes, On D0L systems with immigration, Symbolic representation of piecewise linear functions on the unit interval and application to discrepancy, An extension of Kleene's and Ochmański's theorems to infinite traces, Residual finiteness of a class of semigroups presented by a single relation, \(p\)-adic topology on words, Deterministic sequential functions, Some complexity results for polynomial rational expressions., Regular component decomposition of regular languages., Limit sets of automatic sequences., On the bijective colouring of Cantor trees based on transducers, Testing conformance of a deterministic implementation against a non-deterministic stream X-machine, Many aspects of defect theorems, Unary algebras, semigroups and congruences on free semigroups, Two techniques in the area of the star problem in trace monoids, Some properties of Ising automata, Synchronization of musical words, Finiteness spaces and generalized power series, Spectral theory of regular sequences, Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids, The join of the pseudovarieties of idempotent semigroups and locally trivial semigroups, The word problem for nilpotent inverse monoids, Iterative weighted finite transductions, Conway's work on iteration, On join irreducible \(J\)-trivial semigroups, Valuations, regular expressions, and fractal geometry, Formations of inverse semigroups, Purity results for some arithmetically defined measures, On subsystems of a fuzzy finite state machine, Lamplighter groups and automata, Łukasiewicz language and diagonals of formal series, Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems, Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy, On the rational subsets of the free group, Weighted automata and weighted MSO logics for average and long-time behaviors, Automata methods in transcendence, Recognizability of the support of recognizable series over the semiring of the integers is undecidable, Proper/residually-finite idempotent semirings., Free Kleene algebras with domain, Lexicographic decomposition of \(k\)-valued transducers, On the representation of finite deterministic 2-tape automata, Ostrowski-automatic sequences: theory and applications, On language varieties without Boolean operations, On the computational power of programs over \(\mathsf{BA}_2\) monoid, Theory of reaction automata: a survey, Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity, Colored operads, series on colored operads, and combinatorial generating systems, Automatic sequences based on Parry or Bertrand numeration systems, Every decidable pseudovariety of abelian groups is completely tame, A new approach to the 2-regularity of the \(\ell\)-abelian complexity of 2-automatic sequences, A geometric approach to (semi)-groups defined by automata via dual transducers., A finiteness criterion for inverse semigroups, Infinite behaviour of Petri nets, Recognizable subsets of some partially Abelian monoids, Robustness of Pisot-regular sequences, Space-efficient bimachine construction based on the equalizer accumulation principle, Decimation and interleaving operations in one-sided symbolic dynamics, Functional models of neurobiological processes, On the Hurwitz product of formal power series and automata, Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet, Weighted automata with storage, Testing based on identifiable P systems using cover automata and X-machines, Model checking of linear-time properties in multi-valued systems, A topological shuttle between inequalities and pseudoinequalities, Shift-plethysm, hydra continued fractions, and \(m\)-distinct partitions, Minimal automaton for multiplying and translating the Thue-Morse set, The chromatic Brauer category and its linear representations, Simplicity of augmentation submodules for transformation monoids, Kleene and Büchi theorems for weighted forest languages over M-monoids, Weighted parsing for grammar-based language models over multioperator monoids, Linear weighted tree automata with storage and inverse linear tree homomorphisms, Categories of quantale-valued fuzzy automata: determinization and minimization, What's decidable about weighted automata?, Principal abstract families of weighted tree languages, Weighted operator precedence languages, Multiplicative automatic sequences, Finite automata, Automata and rational expressions, Finite transducers and rational transductions, Weighted automata, Two-dimensional models, Equational theories for automata, Decidability and \(k\)-regular sequences, On the automaticity of the Hankel determinants of a family of automatic sequences, Kleene stars of the plane, polylogarithms and symmetries, On some decidability questions concerning supports of rational series, Support of an algebraic series as the range of a recursive sequence, Uniform and nonuniform recognizability., Automata, Boolean matrices, and ultimate periodicity., On equations for union-free regular languages, Iterated function systems and control languages, Communication complexity method for measuring nondeterminism in finite automata, The star problem and the finite power property in trace monoids: Reductions beyond C4, Character theory of monoids over an arbitrary field., Iterating transducers, Uniform strategies, rational relations and jumping automata, Combination of roots and Boolean operations: an application to state complexity, The complexity of compressing subsegments of images described by finite automata, Opacity of a finite automaton, method of calculation and the Ising chain, A non-ambiguous decomposition of regular languages and factorizing codes, Periodicity vectors for labelled trees, The alphabetic complexity in homomorphic definitions of word, tree and picture languages, Fuzzy recognizers and recognizable sets, Characterizing weighted MSO for trees by branching transitive closure logics, The finite power property in free groups, Some properties of recognizable \(\mathcal Z\)-subsets, A disambiguation algorithm for weighted automata, Hartmanis-Stearns Conjecture on Real Time and Transcendence, Visibly Pushdown Transducers with Look-Ahead, Testing against a non-controllable stream X-machine using state counting, Equivalence in automata theory based on complete residuated lattice-valued logic, Minimization of lattice finite automata and its application to the decomposition of lattice languages, Fuzzy tree automata, Substitutions, abstract number systems and the space filling property, On the complexity of infinite words generated by countable \(q\)-automata, On the fundamental group of self-affine plane tiles, Weighted automata and weighted logics, On alpha-adic expansions in Pisot bases, Freeness of automaton groups vs boundary dynamics, Syndeticity and independent substitutions, Multi-dimensional sets recognizable in all abstract numeration systems, A formal power series approach to the construction of minimal fuzzy automata, The fixed points of logic programs with Herbrand base \({\mathbb{N}}\), Automata and languages generalized to \(\omega\)-continuous semirings, A Disambiguation Algorithm for Finite Automata and Functional Transducers, Infinite fuzzy computations, Improved matrix pair undecidability results, Semirings and pseudo MV algebras, Abstract \(\beta\)-expansions and ultimately periodic representations, Axiomatizing rational power series over natural numbers, Coinduction in Concurrent Timed Systems, Inductive semimodules and the vector modules over them., Automatic sequences and curves over finite fields, Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory, Transforming communicating X-machines into P systems, A simple method for building bimachines from functional finite-state transducers, Groups and semigroups defined by colorings of synchronizing automata, Preference Decomposition and the Expressiveness of Preference Query Languages, Classification of annotation semirings over containment of conjunctive queries, On ideals of quasi-commutative semigroups, Greibach normal form for \(\omega\)-algebraic systems and weighted simple \(\omega\)-pushdown automata, On quotients of formal power series, Learning Weighted Automata, A model learning based testing approach for spiking neural P systems, On the Disambiguation of Weighted Automata, Reducing the local alphabet size in tiling systems by means of 2D comma-free codes, Quasi-automatic semigroups, Weighted simple reset pushdown automata, Decomposition and factorization of chemical reaction transducers, Weighted iterated linear control, On the membership problem for finite automata over symmetric groups, Acts over semigroups, Weighted logics for unranked tree automata, Weighted picture automata and weighted logics, Quantitative vs. weighted automata, Input- or output-unary sweeping transducers are weaker than their 2-way counterparts, On the notion of persistence of excitation for linear switched systems, On lattices of regular sets of natural integers closed under decrementation, Syntactic recognizability of graphs with fuzzy attributes, A note on probabilistic models over strings: the linear algebra approach, Complete κ-reducibility of pseudovarieties of the form DRH, Integer semigroups associated with Dumont-Thomas numeration systems, Minimal realization for fuzzy behaviour: A bicategory-theoretic approach, A short proof of a theorem of Cobham on substitutions, Randomly growing braid on three strands and the Manta Ray, Classes of two-dimensional languages and recognizability conditions, A Unifying Kleene Theorem for Weighted Finite Automata, A complete characterization of deterministic regular liveness properties, Concurrent secrets, Syntactical and automatic properties of sets of polynomials over finite fields, Möbius functions and semigroup representation theory. II: Character formulas and multiplicities., Cobham-Semenov theorem and \(\mathbb N^d\)-subshifts, Sparse and slender subsets of monoids., Bisimulation relations for weighted automata, Another proof of Soittola's theorem, Algebraic recognizability of regular tree languages, Inference of finite-state transducers from regular languages, Linear splicing and syntactic monoid, Representation of a class of nondeterministic semiautomata by canonical words., Characterizing CTL-like logics on finite trees., Sequential?, Recognizability of graph and pattern languages, A generalized Ufnarovski graph, A categorical approach to lattice-valued fuzzy automata, Fuzzy regular languages over finite and infinite words, Combinatorial aspects of continued fractions. (Reprint), Boolean restriction categories and taut monads, The monadic quantifier alternation hierarchy over grids and graphs, Word problems recognisable by deterministic blind monoid automata, On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata, A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic, Maximal bifix decoding, EURACE: A massively parallel agent-based model of the European economy, k-Abelian Equivalence and Rationality, Both Ways Rational Functions, Weighted Automata and Logics on Infinite Graphs, Weighted Symbolic Automata with Data Storage, Solution sets for equations over free groups are EDT0L languages, On the Rademacher Complexity of Weighted Automata, COMPLETELY REDUCIBLE SETS, On the power of circular splicing, Constructing divisions into power groups, Synchronized shuffles, Arithmetic Meyer sets and finite automata, The existential theory of equations with rational constraints in free groups is PSPACE-complete, A theory of computation based on quantum logic. I, Coalgebraising Subsequential Transducers, Unnamed Item, Asymptotic Subword Complexity, Solution Sets for Equations over Free Groups are EDT0L Languages, Recognisable Languages over Monads, On a subclass of context-free groups, Unnamed Item, Unnamed Item, Phénomène de Moser-Newman pour les nombres sans facteur carré, The Synchronization Problem for Locally Strongly Transitive Automata, On the Recognizability of Self-generating Sets, Sul problema di Burnside per i semigruppi e i linguaggi, Representations of numbers and finite automata, Crossability of cancellative Kleene semigroups, Extensions de representations d'algebres, Unnamed Item, Unnamed Item, Unnamed Item, Saturating right congruences, Two-way automaton computations, Bi-infinitary codes, Compositional representation of rational functions, Each regular code is included in a maximal regular code, A geometrical view of the determinization and minimization of finite-state automata, Unnamed Item, Unnamed Item, Notes on finite asynchronous automata, Développement en base $\theta$, répartition modulo un de la suite $(x\theta \sp n)$, n$\ge 0$, langages codés et $\theta$-shift, Model Theoretic Complexity of Automatic Structures (Extended Abstract), Weighted Automata and Weighted Logics with Discounting, Deterministic Caterpillar Expressions, Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages, Deciding whether a relation defined in Presburger logic can be defined in weaker logics, Unnamed Item, A decision method for the recognizability of sets defined by number systems, Unnamed Item, On Generalizations of Weighted Finite Automata and Graphics Applications, Tiling Recognizable Two-Dimensional Languages, Deterministic Two-Dimensional Languages over One-Letter Alphabet, Aperiodicity in Tree Automata, Unnamed Item, A property of biprefix codes, Iteration Semirings, On the Non-deterministic Communication Complexity of Regular Languages, The Synchronization Problem for Strongly Transitive Automata, On the Decidability of the Equivalence for k-Valued Transducers, Hopcroft’s Algorithm and Cyclic Automata, Weak Second‐Order Arithmetic and Finite Automata, Unnamed Item, Monoïde libre et musique : deuxième partie, Hierarchies and reducibilities on regular languages related to modulo counting, Solutions to twisted word equations and equations in virtually free groups, On linear systems and noncommutative rings, PROTECTION AS A GENERAL SYSTEMS PROBLEM, Generalized cancellation-and-permutation properties, regular languages and supports of rational series, Control of discrete-event systems with minimal switchings, -Treeautomata and their relation to weighted context-free grammars, THE LOGIC OF AUTOMATA, Deux propriétés décidables des suites récurrentes linéaires, APERIODIC POINTLIKES AND BEYOND, Unnamed Item, Unnamed Item, The lattice of minimal realizations of response maps over rings, EIGENVALUES OF FIBONACCI STOCHASTIC ADDING MACHINE, Unnamed Item, Unnamed Item, A topoiogical formulation of linguistic typology, Definability of Combinatorial Functions and Their Linear Recurrence Relations, Unnamed Item, Unnamed Item, Framed Versus Unframed Two-Dimensional Languages, Matrix Invariants over Semirings, ON GROUPS AND COUNTER AUTOMATA, 3-Way Composition of Weighted Finite-State Transducers, Facets of Synthesis: Revisiting Church’s Problem, [https://portal.mardi4nfdi.de/wiki/Publication:3883200 Rel�vement d'une mesure ergodique par un codage], Le théorème de transversale rationnelle dans les langages d'arbres, Regular Expressions on Average and in the Long Run, Simulations of Weighted Tree Automata, Series which are both max-plus and min-plus rational are unambiguous, Unnamed Item, Unnamed Item, Unnamed Item, A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata, Left and Right Synchronous Relations, On Negative Bases, On the Decidability of the Equivalence for a Certain Class of Transducers, Partial Conway and Iteration Semiring-Semimodule Pairs, Rational Transformations and a Kleene Theorem for Power Series over Rational Monoids, Quantum Automata Theory – A Review, Valuations of Weighted Automata: Doing It in a Rational Way, CODING PARTITIONS OF REGULAR SETS, Suites algébriques, automates et substitutions, On free inverse monoid languages, Codes and Bernoulli partitions, Decomposing a $k$-valued transducer into $k$ unambiguous ones, Decision problems among the main subfamilies of rational relations, Unambiguous recognizable two-dimensional languages, An Exercise on Fibonacci Representations, On synchronized sequences and their separators, On Conjugacy of Languages, Some Characterization of Recursively Enumerable Sets, Closure under union and composition of iterated rational transductions, Crisp-determinization of weighted tree automata over strong bimonoids, On-line finite automata for addition in some numeration systems, The p-adic Theory of Automata Functions, Feature automata and recognizable sets of feature trees, Polynomial closure of group languages and open sets of the Hall topology, Pattern matching in trace monoids, Model Reduction and Realization Theory of Linear Switched Systems, On multiplicatively dependent linear numeration systems, and periodic points, Pattern-matching problems for 2-dimensional images described by finite automata, Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines, Unnamed Item, Syntactic Nondeterministic Monoids, Recognizable sets of graphs: equivalent definitions and closure properties, Newton series, coinductively: a comparative study of composition, Unnamed Item, Unnamed Item, Rational and Recognisable Power Series, Weighted Automata and Weighted Logics, Applications of Weighted Automata in Natural Language Processing, Unnamed Item, Unnamed Item, Computability by finite automata and pisot bases, Solving trace equations using lexicographical normal forms, Unnamed Item, Reversion of outputs of fuzzy discrete systems, Birecurrent sets, On the algebraicity of Thue–Morse and period-doubling continued fractions, Properties of infinite words : Recent results, Linear numeration systems, θ-developments and finite automata, New results on the generalized star-height problem, Deciding equivalence of finite tree automata, Recognizable sets of numbers in nonstandard bases, Joining k- and l-recognizable sets of natural numbers, On the factorization conjecture, Characterizing regular languages with polynomial densities, On the minimization problem for ω-automata, Some trace monoids where both the Star problem and the Finite Power Property Problem are decidable, Unnamed Item, Rational transductions and complexity of counting problems, Decidability of regular language genus computation, Abelian Invertible Automata, Unnamed Item, Unnamed Item, Unnamed Item, Sur le développement en fraction continue de la série de Baum et Sweet, Unnamed Item, Unnamed Item, General Framework, Number Theoretic Aspects of Regular Sequences, First-Order Logic and Numeration Systems, Unnamed Item, Fair expressions and regular languages over lists, Language acceptability of finite automata based on theory of semi‐tensor product of matrices, Unnamed Item, Cobham's Theorem seen through Büchi's Theorem, The product of rational languages, From Combinatorial Games to Shape-Symmetric Morphisms, Valuations and unambiguity of languages, with applications to fractal geometry, On continuous functions computed by finite automata, Bijective sequential mappings of a free monoid onto another, On semigroups of matrices over the tropical semiring, Systems, scattering and operators, and their connections with number theory, Computing the closure of sets of words under partial commutations, Logically automorphically equivalent knowledge bases models, Languages obtained from infinite words, Two-Sided Strictly Locally Testable Languages, Simulating Finite Eilenberg Machines with a Reactive Engine, On Shuffle Ideals, Radix enumeration of rational languages, The pseudovariety of semigroups of triangular matrices over a finite field, Some decision problems on integer matrices, Krohn-Rhodes complexity pseudovarieties are not finitely based, Unnamed Item, From regular expressions to finite automata^∗, Unnamed Item, Catalan fragile words, Pole placement over integral domains, The cartesian composition of automata, Unnamed Item, The equality problem for rational series with multiplicities in the tropical semiring is undecidable, Asynchronous cellular automata for infinite traces, Automata groups generated by Cayley machines of groups of nilpotency class two, Codes asynchrones, Multisets, heaps, bags, families: What is a multiset?, The closure under division and a characterization of the recognizable $\mathcal {Z}$-subsets, A generalization of automatic sequences, Origin-equivalence of two-way word transducers is in PSPACE, Une critique de la notion de test de processus fondée sur la non séparabilité de certaines classes de langages, Roots and Powers in Regular Languages: Recognizing Nonregular Properties by Finite Automata, Cardinality problems of compositions of morphisms and inverse morphisms, Unnamed Item, Supremal and maximal sublanguages arising in supervisor synthesis problems with partial observations, Weighted Operator Precedence Languages, Unnamed Item, The Power of Programs over Monoids in DA, The entropy and Hausdorff dimension of self-similar sets, Iteration of rational transductions, Asynchronous sliding block maps, Convolution as a Unifying Concept, Specht property for the algebra of upper triangular matrices of size two with a Taft’s algebra action, Ultimately periodic words of rational ω-languages, State-complexity of finite-state devices, state compressibility and incompressibility, Reducibility vs. definability for pseudovarieties of semigroups, Distance desert automata and the star height problem, AbU: a calculus for distributed event-driven programming with attribute-based interaction, The palindromization map, Minimality and identifiability of discrete‐time switched autoregressive exogenous systems, Normality for monoid monomorphisms, Automatic presentations of structures, Decidability Boundaries for the Finite-Image Property of Weighted Finite Automata, Automata and one-dimensional TQFTs with defects, On the category of \(L\)-fuzzy automata, coalgebras and dialgebras, Interference as a computational resource: a tutorial, Bideterministic weighted automata, When variable-length codes meet the field of error detection, The net automaton of a rational expression, The Triple-Pair Construction for Weighted ω-Pushdown Automata, ZAREMBA, SALEM AND THE FRACTAL NATURE OF GHOST DISTRIBUTIONS, Unnamed Item, Identities and transductions, A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices, Weighted Linear Dynamic Logic, Bideterministic weighted automata, On the transition monoid of the Stallings automaton of a subgroup of a free group, Regularity of k-Abelian Equivalence Classes of Fixed Cardinality, Outlier detection in a multiset-valued information system based on rough set theory and granular computing, String matching algorithms and automata, Monodromie unipotente maximale, congruences “à la Lucas” et indépendance algébrique, Eilenberg's variety theorem without Boolean operations, Topologies for error-detecting variable-length codes, The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies, Recognizability in residuated lattices, Propriétés booléennes des langages stochastiques, Unnamed Item, On Kleene algebras, Properties of graphs specified by a regular language, Differential (Monoid) Algebra and More, Circuit complexity of regular languages, Automata Learning: A Categorical Perspective, Complexity of automatic sequences, Properties of graphs specified by a regular language, A technology for reverse-engineering a combinatorial problem from a rational generating function, One-unambiguous regular languages, One-unambiguous regular languages, Locally finite languages, Codes and equations on trees, SC-hyperdecidability of \(\mathbf R\), On Parikh slender context-free languages, Automatic verification of parameterized networks of processes, New types of automata to solve fixed point problems, The group of asynchronous automata and rational homeomorphisms of the Cantor set, Algorithmic questions for real functions, Automata, Borel functions and real numbers in Pisot base, A graphic language based on timing diagrams, Flexible regenerative supervision of sequential behaviour., Trees associated to inverse monoid presentations, Topological properties of omega context-free languages, Asymptotic behavior in a heap model with two pieces, Wadge hierarchy of omega context-free languages, Numeration systems on a regular language: Arithmetic operations, recognizability and formal power series, Direct and dual laws for automata with multiplicities, An Automata Theoretic Approach to Rational Tree Relations, Balanced truncation for linear switched systems, On the regularity of circular splicing languages: a survey and new developments, Realization theory for linear and bilinear switched systems: A formal power series approach, RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA, Automatic Sequences and Generalised Polynomials, Semicorings and Semicomodules, On implementing recognizable transductions, Weak Separation Problem for Tree Languages, A More Reasonable Proof of Cobham’s Theorem, Abstractions Preserving Parameter Confidentiality, Cascade Products and Temporal Logics on Finite Trees, Computing with relational machines, Categories of Automata and Languages Based on a Complete Residuated Lattice, The Relationship Among Fuzzy Languages, Upper Sets and Fuzzy Ordered Monoids, Iterative pairs and multitape automata