Fetching the paper…
Reading the bibliography…
This paper is about certain string-to-string functions, called the polyregular functions.
On relations defined by generalized finite automata
Calvin C Elgot and Jorge E Mezei · 1965
Earlier work this paper cites.
Algebraic theory of machines. i. prime decomposition theorem for finite semigroups and machines
Kenneth Krohn and John Rhodes · 1965
Earlier work this paper cites.
Some definitional suggestions for automata theory
Dana Scott · 1967
Earlier work this paper cites.
An approach to a unified theory of automata
JD Ullman and JE Hopcroft · 1967
Earlier work this paper cites.
A characterization of two-way deterministic classes of languages
Alfred V Aho and Jeffrey D Ullman · 1970
Earlier work this paper cites.
Characterizations of some tape and time complexity classes of turing machines in terms of multihead and auxiliary stack automata
Oscar H Ibarra · 1971
Earlier work this paper cites.
Automata, languages, and machines
Samuel Eilenberg · 1974
Earlier work this paper cites.
Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles
Christian Choffrut · 1977
Earlier work this paper cites.
Serial composition of 2-way finite-state transducers and simple programs on strings
Michal P Chytil and Vojtěch Jákl · 1977
Earlier work this paper cites.
A generalization of ginsburg and rose’s characterization of gsm mappings
Christian Choffrut · 1979
Earlier work this paper cites.
The equivalence problem for deterministic two-way sequential transducers is decidable
Eitan M Gurari · 1982
Earlier work this paper cites.
Parity, circuits, and the polynomial-time hierarchy
Merrick Furst, James B Saxe, and Michael Sipser · 1984
Earlier work this paper cites.
Factorization forests of finite height
Imre Simon · 1990
Earlier work this paper cites.
Minimization of rational word functions
Christophe Reutenauer and Marcel-Paul Schutzenberger · 1991
Earlier work this paper cites.
Complexity Results for Two-Way and Multi-Pebble Automata and their Logics
Noa Globerman and David Harel · 1996
Earlier work this paper cites.
Languages, automata, and logic
Wolfgang Thomas · 1997
Earlier work this paper cites.
A tutorial on the universality and expressiveness of fold
Graham Hutton · 1999
Cited alongside, same era.
Mso definable string transductions and two-way finite-state transducers
Joost Engelfriet and Hendrik Jan Hoogeboom · 2001
Cited alongside, same era.
The descriptive complexity approach to logcfl
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, and Heribert Vollmer · 2001
Cited alongside, same era.
Two-way finite state transducers with nested pebbles
Joost Engelfriet and Sebastian Maneth · 2002
Cited alongside, same era.
Minimizing subsequential transducers: a survey
Christian Choffrut · 2003
Cited alongside, same era.
Typechecking for xml transformers
Tova Milo, Dan Suciu, and Victor Vianu · 2003
Cited alongside, same era.
Streaming transducers for algorithmic verification of single-pass list-processing programs
Rajeev Alur and Pavol Černỳ · 2011
Later among the works it cites.
Graph structure and monadic second-order logic: a language-theoretic approach
Bruno Courcelle and Joost Engelfriet · 2012
Later among the works it cites.
Finite automata, formal logic, and circuit complexity
Howard Straubing · 2012
Later among the works it cites.
Transductions and context-free languages
Jean Berstel · 2013
Later among the works it cites.
From two-way to one-way finite state transducers
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais · 2013
Later among the works it cites.
Enumeration of monadic second-order queries on trees
Wojciech Kazana and Luc Segoufin · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Mso queries on tree decomposable structures are computable with linear delay
Guillaume Bagan · 2006
Cited alongside, same era.
Lectures on the Curry-Howard isomorphism
Morten Heine Sørensen and Pawel Urzyczyn · 2006
Cited alongside, same era.
A combinatorial theorem for trees
Thomas Colcombet · 2007
Cited alongside, same era.
The height of factorization forests
Manfred Kufleitner · 2008
Cited alongside, same era.
From logic to theoretical computer science–an update
Boris A Trakhtenbrot · 2008
Cited alongside, same era.
Factorization forests
Mikołaj Bojańczyk · 2009
Cited alongside, same era.
Regular combinators for string transformations
Rajeev Alur, Adam Freilich, and Mukund Raghothaman · 2014
Later among the works it cites.
One-way definability of sweeping transducers
Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis · 2015
Later among the works it cites.
Aperiodic Two-way Transducers and FO-Transductions
Olivier Carton and Luc Dartois · 2015
Later among the works it cites.
Two-way pebble transducers for partial functions and their composition
Joost Engelfriet · 2015
Later among the works it cites.
First-order definability of rational transductions: An algebraic approach
Emmanuel Filiot, Olivier Gauwin, and Nathan Lhote · 2016
Later among the works it cites.
Transducers, logic and algebra for functions of finite words
Emmanuel Filiot and Pierre-Alain Reynier · 2016
Later among the works it cites.
Regular and first-order list functions
Mikołaj Bojańczyk, Laure Daviaud, and Shankara Narayanan Krishna · 2018
Closest in time.
Regular transducer expressions for regular transformations
Vrunda Dave, Paul Gastin, and Shankara Narayanan Krishna · 2018
Closest in time.
First-order logic and aperiodic languages: A revisionist history
Howard Straubing · 2018
Closest in time.