Cover Image

On the Complexity of Language Membership for Probabilistic Words

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Amarilli, Antoine, Monet, Mikaël, Raphaël, Paul, Salvati, Sylvain
Format:	Preprint
Published:	2025
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

Locality Testing for NFAs is PSPACE-complete
by: Amarilli, Antoine, et al.
Published: (2025)

Out-of-Order Membership in Regular Languages
by: Amarilli, Antoine, et al.
Published: (2026)

Locality and Centrality: The Variety ZG
by: Amarilli, Antoine, et al.
Published: (2021)

Dynamic Membership for Regular Tree Languages
by: Amarilli, Antoine, et al.
Published: (2025)

Constant-Time Dynamic Enumeration of Word Infixes in a Regular Language
by: Amarilli, Antoine, et al.
Published: (2026)

A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata
by: Amarilli, Antoine, et al.
Published: (2024)

Skyline Operators for Document Spanners
by: Amarilli, Antoine, et al.
Published: (2023)

Reversible Transducers over Infinite Words
by: Dartois, Luc, et al.
Published: (2024)

Linear Time Subsequence and Supersequence Regex Matching
by: Amarilli, Antoine, et al.
Published: (2025)

Uniform Membership for Hyperedge Replacement Grammars and Related Decision Problems
by: Pshenitsyn, Tikhon
Published: (2025)

Deterministic pushdown automata can compress some normal sequences
by: Carton, Olivier, et al.
Published: (2022)

Classifying Words with 3-sort Automata
by: Jastrząb, Tomasz, et al.
Published: (2024)

Operational State Complexity of Block Languages
by: Duarte, Guilherme, et al.
Published: (2024)

On the Representation and State Complexity of Block Languages
by: Duarte, Guilherme, et al.
Published: (2024)

Exact Separation of Words via Trace Geometry
by: Chen, Zeyu, et al.
Published: (2026)

Characterization of Isometric Words based on Swap and Mismatch Distance
by: Anselmo, M., et al.
Published: (2024)

Measure Many Quantum Finite Automata on Infinite Words
by: Midya, Abhisek, et al.
Published: (2026)

Structural Abstraction and Refinement for Probabilistic Programs
by: Li, Guanyan, et al.
Published: (2025)

Conservative Perception Models for Probabilistic Verification
by: Cleaveland, Matthew, et al.
Published: (2025)

Word-Representable Graphs and Locality of Words
by: Böll, Philipp, et al.
Published: (2025)

Star Complexity of Parikh Images of Languages over Infinite Alphabets
by: Danieli, Yoav
Published: (2026)

On the Complexity of Computing the Co-lexicographic Width of a Regular Language
by: Becker, Ruben, et al.
Published: (2024)

A Probabilistic Model-Checking Framework for Cognitive Assessment and Training
by: De Maria, Elisabetta, et al.
Published: (2026)

Controller Synthesis for Parametric Timed Games
by: Dahlsen-Jensen, Mikael Bisgaard, et al.
Published: (2025)

On-The-Fly Algorithm for Reachability in Parametric Timed Games (Extended Version)
by: Dahlsen-Jensen, Mikael Bisgaard, et al.
Published: (2024)

Computational Complexity of Alignments
by: Schwanen, Christopher T., et al.
Published: (2026)

Is decidability of the Submonoid Membership Problem closed under finite extensions?
by: Shafrir, Doron
Published: (2024)

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

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

A Complexity Bound for Determinisation of Min-Plus Weighted Automata
by: Almagor, Shaull, et al.
Published: (2026)

Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
by: Wehar, Michael
Published: (2025)

Recursive Prime Factorizations: Dyck Words as Numbers
by: Childress, Ralph L.
Published: (2021)

State Complexity of Shifts of the Fibonacci Word
by: Moradi, Delaram, et al.
Published: (2026)

Mind the Gap: A Formal Investigation of the Relationship Between Log and Model Complexity -- Extended Version
by: Schalk, Patrizia, et al.
Published: (2025)

Refuting Equivalence in Probabilistic Programs with Conditioning
by: Chatterjee, Krishnendu, et al.
Published: (2025)

Equivalence and Similarity Refutation for Probabilistic Programs
by: Chatterjee, Krishnendu, et al.
Published: (2024)

Universally Wheeler Languages
by: Becker, Ruben, et al.
Published: (2025)

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

A Sharper Upper Bound for the Separating Words Problem
by: Dumitru, Bogdan C.
Published: (2025)

Designing and Comparing RPQ Semantics
by: Marsault, Victor, et al.
Published: (2026)