Imagen de Portada

Weighted GKAT: Completeness and Complexity

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Van Koevering, Spencer, Różowski, Wojciech, Silva, Alexandra
Formato:	Preprint
Publicado:	2025
Materias:	Logic in Computer Science Formal Languages and Automata Theory Programming Languages
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Completeness Theorem for Probabilistic Regular Expressions
por: Różowski, Wojciech, et al.
Publicado: (2023)

A Diagrammatic Axiomatisation of Behavioural Distance of Nondeterministic Processes
por: Różowski, Wojciech, et al.
Publicado: (2026)

A cyclic proof system for Guarded Kleene Algebra with Tests (full version)
por: Rooduijn, Jan, et al.
Publicado: (2024)

Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
por: Czerwiński, Wojciech, et al.
Publicado: (2025)

Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
por: Czerwiński, Wojciech, et al.
Publicado: (2022)

Reachability in 3-VASS is Elementary
por: Czerwiński, Wojciech, et al.
Publicado: (2025)

Finding Regular Herbrand Models for CHCs using Answer Set Programming
por: Maire, Gregoire, et al.
Publicado: (2025)

Verifying Asynchronous Hyperproperties in Reactive Systems
por: Beutner, Raven, et al.
Publicado: (2025)

Parametrizing Reads-From Equivalence for Predictive Monitoring
por: Farzan, Azadeh, et al.
Publicado: (2026)

The Decision Problem for Regular First-Order Theories
por: Mathur, Umang, et al.
Publicado: (2024)

Syntactically and semantically regular languages of lambda-terms coincide through logical relations
por: Moreau, Vincent, et al.
Publicado: (2023)

SuperDP: Differential Privacy Refutation via Supermartingales
por: Chatterjee, Krishnendu, et al.
Publicado: (2026)

Towards a Coq-verified Chain of Esterel Semantics
por: Berry, Gérard, et al.
Publicado: (2019)

Complete Test Suites for Automata in Monoidal Closed Categories
por: Kocsis, Bálint, et al.
Publicado: (2024)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
por: Halftermeyer, Pierre
Publicado: (2026)

A Complete Propositional Dynamic Logic for Regular Expressions with Lookahead
por: Nakamura, Yoshiki
Publicado: (2026)

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

Feasability of Learning Weighted Automata on a Semiring
por: Daviaud, Laure, et al.
Publicado: (2023)

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
por: Daviaud, Laure, et al.
Publicado: (2023)

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

Quantitative Weakest Hyper Pre: Unifying Correctness and Incorrectness Hyperproperties via Predicate Transformers
por: Zhang, Linpeng, et al.
Publicado: (2024)

Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
por: Zetzsche, Stefan, et al.
Publicado: (2024)

The Tractability Border of Reachability in Simple Vector Addition Systems with States
por: Chistikov, Dmitry, et al.
Publicado: (2024)

The Complexity of Second-order HyperLTL
por: Frenkel, Hadar, et al.
Publicado: (2023)

Image Reflection on Process Graphs -- A Novel Approach for the Completeness of an Axiomatization of 1-Free Regular Expressions Modulo Bisimilarity
por: Zhang, Yuanrui, et al.
Publicado: (2023)

The Complexity of Generalized HyperLTL with Stuttering and Contexts
por: Regaud, Gaëtan, et al.
Publicado: (2025)

On The Space Complexity of Partial Derivatives of Regular Expressions with Shuffle
por: Ancona, Davide, et al.
Publicado: (2025)

Complexity of Model Checking Second-Order Hyperproperties on Finite Structures
por: Finkbeiner, Bernd, et al.
Publicado: (2026)

Simple grammar bisimilarity, with an application to session type equivalence
por: Poças, Diogo, et al.
Publicado: (2024)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
por: Barloy, Corentin, et al.
Publicado: (2025)

An algebraic theory of ω-regular languages, via μν-expressions
por: Das, Anupam, et al.
Publicado: (2025)

Cyclic system for an algebraic theory of alternating parity automata
por: Das, Anupam, et al.
Publicado: (2025)

A proof theory of right-linear (omega-)grammars via cyclic proofs
por: Das, Anupam, et al.
Publicado: (2024)

Positive First-order Logic on Words and Graphs
por: Kuperberg, Denis
Publicado: (2022)

Function spaces for orbit-finite sets
por: Bojańczyk, Mikołaj, et al.
Publicado: (2024)

An efficient quantifier elimination procedure for Presburger arithmetic
por: Haase, Christoph, et al.
Publicado: (2024)

Counting and Sampling Traces in Regular Languages
por: de Colnet, Alexis, et al.
Publicado: (2025)

The Queue Automaton Revisited
por: Baeten, Jos C. M., et al.
Publicado: (2025)

Simplifying LTL Model Checking Given Prior Knowledge
por: Duret-Lutz, Alexandre, et al.
Publicado: (2025)

Unreliability in Practical Subclasses of Communicating Systems
por: Suresh, Amrita, et al.
Publicado: (2025)