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

DOI10.1007/S10990-013-9097-8MaRDI QIDQ526439zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Kazutaka Matsuda, Kazuhiro Inaba, Keisuke Nakano

Publication date 15 May 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

functional programmingtree automatatree transducersprogram transformationinverse computationprogram inversion

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1612493
• The universal resolving algorithm and its correctness: Inverse computation in a functional language
• scientific article; zbMATH DE number 1953282
• Program inversion for tail recursive functions
• An universal resolving algorithm for inverse computation of lazy languages

Cites work

• scientific article; zbMATH DE number 1808202 (Why is no real title available?)
• scientific article; zbMATH DE number 3740740 (Why is no real title available?)
• scientific article; zbMATH DE number 176135 (Why is no real title available?)
• scientific article; zbMATH DE number 1953282 (Why is no real title available?)
• scientific article; zbMATH DE number 2043532 (Why is no real title available?)
• scientific article; zbMATH DE number 5033861 (Why is no real title available?)
• A comparison of pebble tree transducers with macro tree transducers
• A grammar-based approach to invertible programs
• A needed narrowing strategy
• An universal resolving algorithm for inverse computation of lazy languages
• Attribute grammar inversion and source-to-source translation
• Composition of functions with accumulating parameters
• Deaccumulation techniques for improving provability
• Deforestation: Transforming programs to eliminate trees
• Functional and Logic Programming
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Macro forest transducers
• Macro tree transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• 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
• Program inversion for tail recursive functions
• Proving and applying program transformations expressed with second-order patterns
• The Complexity of Tree Transducer Output Languages
• The concept of a supercompiler
• The narrowing-driven approach to functional logic program specialization
• Time and space complexity of inside-out macro languages
• Tupling calculation eliminates multiple data traversals
• Typechecking for XML transformers
• Types and higher-order recursion schemes for verification of higher-order programs
• Undecidable properties of deterministic top-down tree transducers

Cited in

(4)

• Functionality of compositions of top-down tree transducers is decidable
• How to decide functionality of compositions of top-down tree transducers
• Computing Inverse ST in Linear Complexity
• Decision problems of tree transducers with origin

Describes a project that uses

Uses Software

• SmallCheck
• Haskell

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

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