The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

• URL: http://arxiv.org/abs/2605.30389v1
• Date: Thu, 28 May 2026 11:19:25 GMT
• Title: The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory
• Abstract summary: This note formulates the problem of computing the inclusion depth of a pattern language.<n>The central open question is whether the inclusion depth ID_Sigma(p) is computable for every pattern p over every finite alphabet Sigma.<n>A simple conjectured formula, ID_Sigma(p) = 2|p| - #var(p) - 1, would imply a linear-time algorithm.
• Score: 7.317669651319179
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Pattern languages are a classical model in formal language theory and algorithmic learning theory. This note formulates the problem of computing the inclusion depth of a pattern language: the length of the longest strict inclusion chain from the universal pattern language to the language generated by a given pattern. Inclusion depth captures the mind-change complexity of pattern identification from positive data. The central open question is whether the inclusion depth ID_Sigma(p) is computable for every pattern p over every finite alphabet Sigma with at least two symbols, and whether it is computable in polynomial time. A simple conjectured formula, ID_Sigma(p) = 2|p| - #var(p) - 1, would imply a linear-time algorithm. The problem connects pattern language inclusion, combinatorics on words, language identification in the limit, and mind-change-bounded learning.

Related papers

• An Algebraic View of the Expressivity of Recurrent Language Models [50.88598486616582]
  The paper develops a unified algebraic account of the expressivity of recurrent neural networks.<n>The same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization.
  arXiv  Detail & Related papers  (2026-06-01T06:47:58Z)
• Logic-of-Thought: Empowering Large Language Models with Logic Programs for Solving Puzzles in Natural Language [67.51318974970985]
  Solving puzzles in natural language poses a long-standing challenge in AI.<n>We propose Logic-of-Thought, a framework that bridges large language models with logic programming.<n>We evaluate our method on various grid puzzles and dynamic puzzles involving actions, demonstrating near-perfect accuracy across all tasks.
  arXiv  Detail & Related papers  (2025-05-22T01:37:40Z)
• Faster Algorithms for Agnostically Learning Disjunctions and their Implications [37.35692862344027]
  We study the algorithmic task of learning Boolean disjunctions in the distribution-free PAC model.<n>We develop an agnostic learner for this concept class with complexity $2tildeO(n1/2)$.
  arXiv  Detail & Related papers  (2025-04-21T17:16:14Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  We train and evaluate neural networks directly as binary classifiers of strings.<n>We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures.<n>Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Are Language Models Puzzle Prodigies? Algorithmic Puzzles Unveil Serious Challenges in Multimodal Reasoning [24.386388107656334]
  This paper introduces the novel task of multimodal puzzle solving, framed within the context of visual question-answering. We present a new dataset, AlgoVQA, designed to challenge and evaluate the capabilities of multimodal language models in solving algorithmic puzzles.
  arXiv  Detail & Related papers  (2024-03-06T17:15:04Z)
• Implementing Dynamic Programming in Computability Logic Web [0.0]
  We present a novel definition of an algorithm and its corresponding algorithm language called CoLweb. CoLweb forces us to a high-level, proof-carrying, distributed-style approach to algorithm design for both non-distributed computing and distributed one. We refine Horn clause definitions into two kinds: blind-univerally-quantified (BUQ) ones and parallel-universally-quantified (PUQ) ones.
  arXiv  Detail & Related papers  (2023-04-04T05:33:43Z)
• End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking [52.05847268235338]
  We show how machine learning systems can perform logical extrapolation without overthinking problems. We propose a recall architecture that keeps an explicit copy of the problem instance in memory so that it cannot be forgotten. We also employ a progressive training routine that prevents the model from learning behaviors that are specific to number and instead pushes it to learn behaviors that can be repeated indefinitely.
  arXiv  Detail & Related papers  (2022-02-11T18:43:28Z)
• Learning Union of Integer Hypercubes with Queries (Technical Report) [0.0]
  We study the problem of learning a finite union of integer hypercubes over the d-dimensional integer lattice. Over a non-fixed dimension, the problem subsumes the problem of learning DNF formulas. Our problem has a natural application to the problem of monadic decomposition of quantifier-free integer linear arithmetic formulas.
  arXiv  Detail & Related papers  (2021-05-27T11:39:10Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
  arXiv  Detail & Related papers  (2020-02-06T19:56:15Z)
• A Simple Joint Model for Improved Contextual Neural Lemmatization [60.802451210656805]
  We present a simple joint neural model for lemmatization and morphological tagging that achieves state-of-the-art results on 20 languages. Our paper describes the model in addition to training and decoding procedures.
  arXiv  Detail & Related papers  (2019-04-04T02:03:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.