Cover Image

Deterministic Weighted Automata under Partial Observability

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Michaliszyn, Jakub, Otop, Jan
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Learning Tree Automata with Term Rewriting
by: Kopystiański, Jakub, et al.
Published: (2026)

Simulating Weighted Automata over Sequences and Trees with Transformers
by: Rizvi, Michael, et al.
Published: (2024)

Nonuniform Deterministic Finite Automata over finite algebraic structures
by: Idziak, Paweł M., et al.
Published: (2025)

On the Dynamics of Bounded-Degree Automata Networks
by: Aracena, Julio, et al.
Published: (2025)

Deterministic constructions of high-dimensional sets with small dispersion
by: Ullrich, Mario, et al.
Published: (2019)

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
by: Yamakami, Tomoyuki
Published: (2022)

An XOR Lemma for Deterministic Communication Complexity
by: Iyer, Siddharth, et al.
Published: (2024)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
by: Samar, Sahil, et al.
Published: (2026)

Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
by: Mackenzie, Simon, et al.
Published: (2024)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
by: Nkosi, Thami
Published: (2025)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2023)

On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs
by: Khadiev, Kamil
Published: (2016)

Partial and weighted matrix multiplication
by: Vrana, Péter
Published: (2024)

On the Holographic Geometry of Deterministic Computation
by: Nye, Logan
Published: (2025)

Visibly Recursive Automata
by: Dubrulle, Kévin, et al.
Published: (2026)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Deterministic Depth-4 PIT and Normalization
by: Guo, Zeyu, et al.
Published: (2025)

Fast Simulation of Cellular Automata by Self-Composition
by: Natal, Joseph, et al.
Published: (2024)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

PFCS: Prime Factorization Cache System for Deterministic Data Relationship Discovery
by: Le, Duy
Published: (2025)

Deterministic list decoding of Reed-Solomon codes
by: Chatterjee, Soham, et al.
Published: (2025)

One-Way Communication Complexity of Partial XOR Functions
by: Podolskii, Vladimir V., et al.
Published: (2023)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Active Automata Learning with Advice
by: Fica, Michał, et al.
Published: (2025)

On the Approximate Non-Deterministic Degree of Total Boolean Functions
by: Pednekar, Samruddhi, et al.
Published: (2026)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
by: Chen, Shengminjie, et al.
Published: (2026)

Maximal Length Cellular Automata : A Survey
by: Adak, Sumit, et al.
Published: (2024)

Complexity of Unary Exclusive Nondeterministic Finite Automata
by: Kutrib, Martin, et al.
Published: (2024)

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
by: Hair, Isaac M., et al.
Published: (2025)

Local consistency as a reduction between constraint satisfaction problems
by: Dalmau, Victor, et al.
Published: (2023)

Encoding Co-Lex Orders of Finite-State Automata in Linear Space
by: Becker, Ruben, et al.
Published: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
by: Yamakami, Tomoyuki
Published: (2021)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
by: Yamakami, Tomoyuki
Published: (2023)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$
by: Hecht, Yahli, et al.
Published: (2025)