Cover Image

A Complexity Bound for Determinisation of Min-Plus Weighted Automata

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Almagor, Shaull, Arbel, Guy, Sheinvald, Sarai
Format:	Preprint
Published:	2026
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Determinization of Min-Plus Weighted Automata is Decidable
by: Almagor, Shaull, et al.
Published: (2025)

Unambiguisability and Register Minimisation of Min-Plus Models
by: Almagor, Shaull, et al.
Published: (2025)

Quantitative Semantics for Jumping Automata
by: Almagor, Shaull, et al.
Published: (2024)

A Factorization Theorem for Forest Algebras
by: Almagor, Shaull, et al.
Published: (2026)

Two-Way One-Counter Nets Revisited
by: Almagor, Shaull, et al.
Published: (2024)

Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata
by: Acharya, Rohan, et al.
Published: (2024)

Box-Reachability in Vector Addition Systems
by: Almagor, Shaull, et al.
Published: (2025)

Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
by: Jecker, Ismaël, et al.
Published: (2023)

Simulation by Rounds of Letter-to-Letter Transducers
by: Nassar, Antonio Abu, et al.
Published: (2021)

Localising Stochasticity in Weighted Automata
by: Agarwal, Smayan, et al.
Published: (2026)

Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
by: Okudono, Takamasa, et al.
Published: (2024)

Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata
by: Mazowiecki, Filip, et al.
Published: (2025)

Weighted Automata and Regular Expressions for Financial Systems
by: Droste, Manfred, et al.
Published: (2026)

Weighted Tree Automata -- May it be a little more?
by: Fülöp, Zoltán, et al.
Published: (2022)

Optimal Approximate Minimization of One-Letter Weighted Finite Automata
by: Lacroce, Clara, et al.
Published: (2023)

Learning Weighted Automata over Number Rings, Concretely and Categorically
by: Aristote, Quentin, et al.
Published: (2025)

Descriptional Complexity of Finite Automata -- Selected Highlights
by: Salomaa, Arto, et al.
Published: (2023)

Reversible Weighted Automata over Finite Rings and Monoids with Commuting Idempotents
by: Kostolányi, Peter, et al.
Published: (2026)

Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
by: Drabik, Karolina, et al.
Published: (2025)

Mathematical Approach in Automata and Automata Association
by: Maciel, Sergio Henrique
Published: (2020)

Probabilistic Programming Meets Automata Theory: Exact Inference using Weighted Automata
by: Geißler, Dominik, et al.
Published: (2025)

Automata on Graph Alphabets
by: Bazille, Hugo, et al.
Published: (2026)

Weighted Automata for Exact Inference in Discrete Probabilistic Programs
by: Geißler, Dominik, et al.
Published: (2025)

On Shuffling and Splitting Automata
by: Cunningham, Ignacio Mollo
Published: (2024)

Explorable Parity Automata
by: Hazard, Emile, et al.
Published: (2024)

Quantitative Language Automata
by: Henzinger, Thomas A., et al.
Published: (2025)

Asynchronism in Cellular Automata
by: Gautam, Virendra Kumar
Published: (2025)

Corrections to A Menagerie of Timed Automata
by: Keiren, Jeroen J. A., et al.
Published: (2016)

A Unifying Approach to Picture Automata
by: Meeres, Yvo Ad, et al.
Published: (2025)

Nominal Automata with Name Deallocation
by: Prucker, Simon, et al.
Published: (2026)

History-deterministic Parikh Automata
by: Erlich, Enzo, et al.
Published: (2022)

Saturation Problems for Families of Automata
by: Bohn, León, et al.
Published: (2025)

Determinism in Multi-Soliton Automata
by: Bordihn, Henning, et al.
Published: (2024)

Simulations for Event-Clock Automata
by: Akshay, S, et al.
Published: (2022)

History-Deterministic Büchi Automata are Succinct
by: Casares, Antonio, et al.
Published: (2026)

Hyper-Minimization for Deterministic Register Automata
by: Li, Yong, et al.
Published: (2026)

Finite Automata for Efficient Graph Recognition
by: Drewes, Frank, et al.
Published: (2024)

Universality Frontier for Asynchronous Cellular Automata
by: Baburin, Ivan, et al.
Published: (2025)

Simulation Limitations of Affine Cellular Automata
by: Hudcová, Barbora, et al.
Published: (2023)

QuAK: Quantitative Automata Kit
by: Chalupa, Marek, et al.
Published: (2024)