Learning local transductions is hard

DOI10.1007/s10849-004-2115-9zbMath1067.68151OpenAlexW1967761861MaRDI QIDQ1770836

Martin Jansche

Publication date: 7 April 2005

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10849-004-2115-9

zbMATH Keywords

combinatorial optimizationnatural language processingBoolean satisfiabilityformal languagesmachine learningNP completenessrational transductionsletter-to-sound rules

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Natural language processing (68T50)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructing optimal binary decision trees is NP-complete
• Toward efficient agnostic learning
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• A theory of the learnable
• Inference of Reversible Languages
• The minimum consistent DFA problem cannot be approximated within any polynomial
• The String-to-String Correction Problem
• Language identification in the limit

This page was built for publication: Learning local transductions is hard