Explorability in Pushdown Automata

• URL: http://arxiv.org/abs/2511.04048v1
• Date: Thu, 06 Nov 2025 04:35:22 GMT
• Title: Explorability in Pushdown Automata
• Authors: Ayaan Bedi, Karoliina Lehtinen,
• Abstract summary: We study explorability, a measure of nondeterminism in pushdown automata, which generalises history-determinism.<n>We prove that explorable PDAs can be doubly exponentially more succinct than history-deterministic ones.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study explorability, a measure of nondeterminism in pushdown automata, which generalises history-determinism. An automaton is k-explorable if, while reading the input, it suffices to follow k concurrent runs, built step-by-step based only on the input seen so far, to construct an accepting one, if it exists. We show that the class of explorable PDAs lies strictly between history-deterministic and fully nondeterministic PDAs in terms of both expressiveness and succinctness. In fact increasing explorability induces an infinite hierarchy: each level k defines a strictly more expressive class than level k-1, yet the entire class remains less expressive than general nondeterministic PDAs. We then introduce a parameterized notion of explorability, where the number of runs may depend on input length, and show that exponential explorability precisely captures the context-free languages. Finally, we prove that explorable PDAs can be doubly exponentially more succinct than history-deterministic ones, and that the succinctness gap between deterministic and 2-explorable PDAs is not recursively enumerable. These results position explorability as a robust and operationally meaningful measure of nondeterminism for pushdown systems.

Related papers

• GSSF: Generalized Structural Sparse Function for Deep Cross-modal Metric Learning [51.677086019209554]
  We propose a Generalized Structural Sparse to capture powerful relationships across modalities for pair-wise similarity learning. The distance metric delicately encapsulates two formats of diagonal and block-diagonal terms. Experiments on cross-modal and two extra uni-modal retrieval tasks have validated its superiority and flexibility.
  arXiv  Detail & Related papers  (2024-10-20T03:45:50Z)
• Quality Diversity for Robot Learning: Limitations and Future Directions [6.818634856205417]
  Quality Diversity (QD) has shown great success in discovering high-performing, diverse policies for robot skill learning. We argue that new paradigms must be developed to facilitate open-ended search and generalizability.
  arXiv  Detail & Related papers  (2024-07-09T23:29:54Z)
• From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practice [0.0]
  We focus on Learned Sorted Set Dictionaries. We propose a novel paradigm that, complementing known specialized ones, can produce Learned versions of any Sorted Set Dictionary.
  arXiv  Detail & Related papers  (2023-09-02T13:52:53Z)
• Algorithms for Weighted Pushdown Automata [96.29471304123844]
  Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks.<n>We develop novel algorithms that operate directly on WPDAs.
  arXiv  Detail & Related papers  (2022-10-13T10:21:31Z)
• Supporting Vision-Language Model Inference with Confounder-pruning Knowledge Prompt [71.77504700496004]
  Vision-language models are pre-trained by aligning image-text pairs in a common space to deal with open-set visual concepts. To boost the transferability of the pre-trained models, recent works adopt fixed or learnable prompts. However, how and what prompts can improve inference performance remains unclear.
  arXiv  Detail & Related papers  (2022-05-23T07:51:15Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  Complex Event Recognition (CER) systems have become popular in the past two decades due to their ability to "instantly" detect patterns on real-time streams of events. There is a lack of methods for forecasting when a pattern might occur before such an occurrence is actually detected by a CER engine. We present a formal framework that attempts to address the issue of Complex Event Forecasting.
  arXiv  Detail & Related papers  (2021-09-01T09:52:31Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  We discuss an alternative approach to novelty estimation, dubbed Behavior Recognition based Novelty Search (BR-NS) BR-NS does not require an archive, makes no assumption on the metrics that can be defined in the behavior space and does not rely on nearest neighbours search. We conduct experiments to gain insight into its feasibility and dynamics as well as potential advantages over archive-based NS in terms of time complexity.
  arXiv  Detail & Related papers  (2021-04-08T17:31:34Z)
• GOLD-NAS: Gradual, One-Level, Differentiable [100.12492801459105]
  We propose a novel algorithm named Gradual One-Level Differentiable Neural Architecture Search (GOLD-NAS) It introduces a variable resource constraint to one-level optimization so that the weak operators are gradually pruned out from the super-network.
  arXiv  Detail & Related papers  (2020-07-07T10:37:49Z)
• Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions [25.249892204626583]
  inconsistency and incomplete information are ubiquitous in real-world datasets. We propose the notion of "Certain Predictions" (CP) CPClean can significantly outperform existing techniques in terms of classification accuracy with mild manual cleaning effort.
  arXiv  Detail & Related papers  (2020-05-11T13:58:52Z)

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.