First-order definable string transformations

DOI10.4230/LIPICS.FSTTCS.2014.147MaRDI QIDQ2978509zbMATH OpenOpenAlexFDO

Authors Emmanuel Filiot, Shankara Narayanan Krishna, Ashutosh Trivedi

Publication date 25 April 2017

Full work available at URL https://arxiv.org/abs/1406.7824

zbMATH Keywords

first-order logicstreaming string transducers

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Abstract: The connection between languages defined by computational models and logic for languages is well-studied. Monadic second-order logic and finite automata are shown to closely correspond to each-other for the languages of strings, trees, and partial-orders. Similar connections are shown for first-order logic and finite automata with certain aperiodicity restriction. Courcelle in 1994 proposed a way to use logic to define functions over structures where the output structure is defined using logical formulas interpreted over the input structure. Engelfriet and Hoogeboom discovered the corresponding "automata connection" by showing that two-way generalised sequential machines capture the class of monadic-second order definable transformations. Alur and Cerny further refined the result by proposing a one-way deterministic transducer model with string variables---called the streaming string transducers---to capture the same class of transformations. In this paper we establish a transducer-logic correspondence for Courcelle's first-order definable string transformations. We propose a new notion of transition monoid for streaming string transducers that involves structural properties of both underlying input automata and variable dependencies. By putting an aperiodicity restriction on the transition monoids, we define a class of streaming string transducers that captures exactly the class of first-order definable transformations.

Recommendations

• FO-definable transformations of infinite strings
• From monadic second-order definable string transformations to transducers
• Aperiodic string transducers
• MSO definable string transductions and two-way finite-state transducers
• Aperiodic string transducers

Cited in

(12)

• One-way resynchronizability of word transducers
• Aperiodic string transducers
• A circuit complexity approach to transductions
• Regular transformations of infinite strings
• Intelligent Processing of an Unrestricted Text in First Order String Calculus
• scientific article; zbMATH DE number 7003194 (Why is no real title available?)
• FO-definable transformations of infinite strings
• Aperiodic string transducers
• Copyful streaming string transducers
• The many facets of string transducers (invited talk)
• From monadic second-order definable string transformations to transducers
• From two-way transducers to regular function expressions

This page was built for publication: First-order definable string transformations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978509)