From Nondeterministic to Multi-Head Deterministic Finite-State Transducers

DOI10.4230/LIPICS.ICALP.2019.127MaRDI QIDQ5092329zbMATH OpenOpenAlexFDO

Authors Martin Raszyk, Dmitriy Traytel, David Basin

Publication date 21 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10703/pdf/LIPIcs-ICALP-2019-127.pdf/

zbMATH Keywords

finite transducersformal languagesmulti-head automatanondeterminism

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• From two-way to one-way finite state transducers
• FINITELY SUBSEQUENTIAL TRANSDUCERS
• Determinization of transducers over finite and infinite words.
• scientific article; zbMATH DE number 1929941
• MSO definable string transductions and two-way finite-state transducers

Cites work

• k + 1 Heads Are Better than k
• Almost event-rate independent monitoring
• Complexity of multi-head finite automata: origins and directions
• From two-way to one-way finite state transducers
• scientific article; zbMATH DE number 1405653 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• On tape-bounded complexity classes and multihead finite automata
• On the expressiveness of TPTL and MTL
• Timed regular expressions

Cited in

(2)

• Multi-head monitoring of metric temporal logic
• scientific article; zbMATH DE number 2081051 (Why is no real title available?)

This page was built for publication: From Nondeterministic to Multi-Head Deterministic Finite-State Transducers

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