On Relations Defined by Generalized Finite Automata

DOI10.1147/rd.91.0047zbMath0135.00704OpenAlexW1965306495MaRDI QIDQ5507511

Calvin C. Elgot, J. E. Mezei

Publication date: 1965

Published in: IBM Journal of Research and Development (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1147/rd.91.0047

zbMATH Keywords

mathematical logic

Related Items

Semantic Foundations for Deterministic Dataflow and Stream Processing ⋮ A general theory of translation ⋮ Maximin sequential-like machines and chains ⋮ Rational and Recognisable Power Series ⋮ Komplexität von Algorithmen mit Anwendung auf die Analysis ⋮ Characterizations of transductions defined by abstract families of transducers ⋮ The hardest language for grammars with context operators ⋮ When variable-length codes meet the field of error detection ⋮ Abelian Invertible Automata ⋮ Unnamed Item ⋮ Topologies for error-detecting variable-length codes ⋮ Jump complexity of finite automata with translucent letters ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learning two-tape automata from queries and counterexamples ⋮ Unnamed Item ⋮ Resynchronizing Classes of Word Relations ⋮ Unnamed Item ⋮ A GENERAL NOTION OF UNIFORM STRATEGIES ⋮ Abstract families of relations ⋮ CHANNEL SYNTHESIS FOR FINITE TRANSDUCERS ⋮ ITERATION OF INVERTIBLE TRANSDUCTIONS ⋮ On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers ⋮ Abstract families of relations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Automata Theoretic Approach to Rational Tree Relations ⋮ Closure properties of synchronized relations ⋮ On Synthesis of Resynchronizers for Transducers ⋮ Unnamed Item ⋮ On implementing recognizable transductions ⋮ Unnamed Item ⋮ Iterative pairs and multitape automata ⋮ Closure under union and composition of iterated rational transductions ⋮ Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits ⋮ Visibly Pushdown Transducers with Look-Ahead ⋮ Rational equivalence relations ⋮ Representation of rational functions with prefix and suffix codings ⋮ Multi-sequential Word Relations ⋮ Deterministic Ordered Restarting Automata that Compute Functions ⋮ Prognosis of \(\omega\)-languages for the diagnosis of *-languages: a topological perspective ⋮ Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable ⋮ Equivalences and transformations of regular systems - applications to recursive program schemes and grammars ⋮ Easy multiplications. I: The realm of Kleene's theorem ⋮ Linearly bounded infinite graphs ⋮ Unnamed Item ⋮ Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory ⋮ A unified framework for disambiguating finite transductions ⋮ Lamplighter groups and automata ⋮ Familles de langages fermées par crochet ouvert ⋮ Sur les générateurs algébriques et linéaires ⋮ Unnamed Item ⋮ Visibly pushdown transducers ⋮ The growth ratio of synchronous rational relations is unique ⋮ Unnamed Item ⋮ Deterministic synchronization of automata with bounded delay ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ Some decisional problems on rational relations ⋮ Unnamed Item ⋮ Quasi-automatic semigroups ⋮ Multi-grain Relations ⋮ On factors of synchronized sequences ⋮ On the transition graphs of Turing machines. ⋮ Independance forte de certaines opérations ⋮ Synchronizing relations on words ⋮ Unnamed Item ⋮ In memoriam Calvin C. Elgot ⋮ Formes de langages et de grammaires ⋮ Unnamed Item ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ An automaton generating series of graphs ⋮ ALGORITHMS FOR THE JOIN AND AUTO-INTERSECTION OF MULTI-TAPE WEIGHTED FINITE-STATE MACHINES ⋮ Cyclic rational transductions and polynomials of rational functions ⋮ Lexicographic decomposition of \(k\)-valued transducers ⋮ On the representation of finite deterministic 2-tape automata ⋮ Regular languages of nested words: fixed points, automata, and synchronization ⋮ Langages satures et cônes decroissants. Langages et cônes bifideles ⋮ Complete symmetry in d2l systems and cellular automata ⋮ Clocks in dataflow languages ⋮ Multi-Sequential Word Relations ⋮ A canonical automaton for one-rule length-preserving string rewrite systems ⋮ Synchronized rational relations of finite and infinite words ⋮ Unnamed Item ⋮ Confluent linear numeration systems ⋮ Two iteration theorems for some families of languages ⋮ Transductions de séries formelles ⋮ One counter languages and the IRS condition ⋮ Familles de langages translatables et fermées par crochet ⋮ Transductions des langages de Chomsky ⋮ Families of automata characterizing context-sensitive languages ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ The inclusion of the substitution closure of linear and one-counter languages in the largest sub-AFL of the family of algebraic languages is proper ⋮ Comparing language operations ⋮ Rational relations having a rational trace on each finite intersection of rational relations ⋮ Sur les rélations rationnelles entre monoides libres ⋮ Analyse und Synthese von asynchronen ND-Automaten ⋮ Sur une variante des fonctions séquentielles ⋮ One way finite visit automata ⋮ Document Spanners ⋮ Rational Selecting Relations and Selectors ⋮ Opérations de cylindre et applications séquentielles gauches inverses ⋮ A new proof of two theorems about rational transductions ⋮ Semi-synchronous transductions ⋮ Une propriété de Hankel des rélations fonctionnelles entre monoides libres ⋮ Overlap-free words and finite automata ⋮ Maximin sequential chains ⋮ Both Ways Rational Functions ⋮ Left and Right Synchronous Relations ⋮ Pure grammars and pure languages† ⋮ Small overlap monoids. II: Automatic structures and normal forms. ⋮ Syntactic operators on full semiAFLs ⋮ Sets recognized by n-tape automata ⋮ A construction on finite automata that has remained hidden ⋮ Equidivisible Kleene monoids and the Elgot-Mezei theorem ⋮ Multitape finite automata with rewind instructions ⋮ Enumeration des graphes planaires à l'aide des séries formelles en variables non commutatives ⋮ Automata and rational expressions ⋮ Finite transducers and rational transductions ⋮ Minimization algorithms for sequential transducers ⋮ Variable-length codes independent or closed with respect to edit relations ⋮ Calvin C. Elgot (1922-1980) ⋮ Decision problems among the main subfamilies of rational relations ⋮ Relations rationnelles infinitaires ⋮ Iterating transducers ⋮ Uniform strategies, rational relations and jumping automata ⋮ Theoretical and implementational aspects of the formal language server (LaSer) ⋮ Robustness of synchronous communication protocols with delay for decentralized discrete-event control ⋮ Iteration of rational transductions ⋮ Asynchronous sliding block maps ⋮ Modelization of deterministic rational relations ⋮ AUTOMATIC CONVERSION FROM FIBONACCI REPRESENTATION TO REPRESENTATION IN BASE φ, AND A GENERALIZATION ⋮ On synchronized sequences and their separators ⋮ Distances between languages and reflexivity of relations