Polynomial-time inverse computation for accumulative functions with multiple data traversals

DOI10.1007/s10990-013-9097-8zbMath1360.68366OpenAlexW1998594782WikidataQ59271114 ScholiaQ59271114MaRDI QIDQ526439

Kazutaka Matsuda, Keisuke Nakano, Kazuhiro Inaba

Publication date: 15 May 2017

Published in: Higher-Order and Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10990-013-9097-8

zbMATH Keywords

program transformationtree automatafunctional programmingtree transducersinverse computationprogram inversion

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Functional programming and lambda calculus (68N18) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (3)

Decision Problems of Tree Transducers with Origin ⋮ How to decide functionality of compositions of top-down tree transducers ⋮ Functionality of compositions of top-down tree transducers is decidable

Uses Software

• Haskell
• SmallCheck

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of typechecking top-down XML transformations
• Perspectives of systems informatics. 6th international Andrei Ershov memorial conference, PSI 2006, Novosibirsk, Russia, June 27--30, 2006. Revised papers
• Deaccumulation techniques for improving provability
• Deforestation: Transforming programs to eliminate trees
• Macro forest transducers
• Macro tree transducers
• Attribute grammar inversion and source-to-source translation
• Proving and applying program transformations expressed with second-order patterns
• Undecidable properties of deterministic top-down tree transducers
• Typechecking for XML transformers
• A comparison of pebble tree transducers with macro tree transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• The Complexity of Tree Transducer Output Languages
• An Universal Resolving Algorithm for Inverse Computation of Lazy Languages
• A needed narrowing strategy
• A Grammar-Based Approach to Invertible Programs
• The concept of a supercompiler
• Time and space complexity of inside-out macro languages
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Composition of functions with accumulating parameters
• Types and higher-order recursion schemes for verification of higher-order programs
• Functional and Logic Programming
• Tupling calculation eliminates multiple data traversals
• Program Inversion for Tail Recursive Functions
• The narrowing-driven approach to functional logic program specialization

This page was built for publication: Polynomial-time inverse computation for accumulative functions with multiple data traversals