Copertina

Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Wehar, Michael
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Formal Languages and Automata Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Undecidability of the Emptiness Problem for Weak Models of Distributed Computing
di: Principato, Flavio T., et al.
Pubblicazione: (2025)

A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity
di: Mengel, Stefan, et al.
Pubblicazione: (2024)

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

Syntax Repair as Language Intersection
di: Considine, Breandan
Pubblicazione: (2025)

Languages of Boundedly-Ambiguous Vector Addition Systems with States
di: Czerwiński, Wojciech, et al.
Pubblicazione: (2025)

A Tree Sampler for Bounded Context-Free Languages
di: Considine, Breandan
Pubblicazione: (2024)

Bounded treewidth, multiple context-free grammars, and downward closures
di: Aiswarya, C., et al.
Pubblicazione: (2025)

Inform: From Compartmental Models to Stochastic Bounded Counter Machines
di: Leys, Tim, et al.
Pubblicazione: (2024)

Computational Complexity of Alignments
di: Schwanen, Christopher T., et al.
Pubblicazione: (2026)

Time for Timed Monitorability
di: Grosen, Thomas M., et al.
Pubblicazione: (2025)

On the Complexity of Language Membership for Probabilistic Words
di: Amarilli, Antoine, et al.
Pubblicazione: (2025)

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

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

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

Separability and Non-Determinizability of WSTS
di: Czerwiński, Wojciech, et al.
Pubblicazione: (2023)

Invariants and Home Spaces in Transition Systems and Petri Nets
di: Memmi, Gerard
Pubblicazione: (2023)

Iterating Non-Aggregative Structure Compositions
di: Bozga, Marius, et al.
Pubblicazione: (2025)

Non-Global Parikh Tree Automata
di: Herrmann, Luisa, et al.
Pubblicazione: (2024)

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

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

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

You May Delay, but Time Will Not: Timed Games Under Delayed Control
di: Larsen, Kim G., et al.
Pubblicazione: (2025)

Non-deterministic asynchronous automata games and their undecidability
di: Adsul, Bharat, et al.
Pubblicazione: (2024)

Non-interference analysis of bounded labeled Petri nets
di: Ran, Ning, et al.
Pubblicazione: (2025)

Semiflows, Home Spaces, and Home States, Applications to the Analysis of Parameterized Petri Nets
di: Memmi, Gerard
Pubblicazione: (2025)

Parametric Timed Pattern Matching
di: Waga, Masaki, et al.
Pubblicazione: (2019)

Probabilistic Finite Automaton Emptiness is undecidable
di: Rote, Günter
Pubblicazione: (2024)

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

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

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

On Decidability Timed Automata with 2 Parametric Clocks
di: Bersani, Marcello M., et al.
Pubblicazione: (2025)

Compositional Abstraction for Timed Systems with Broadcast Synchronization
di: Chen, Hanyue, et al.
Pubblicazione: (2025)

Learning Deterministic Multi-Clock Timed Automata
di: Teng, Yu, et al.
Pubblicazione: (2024)

Reasoning about Rare-Event Reachability in Stochastic Vector Addition Systems via Affine Vector Spaces
di: Jeppson, Joshua, et al.
Pubblicazione: (2025)

Formalized Run-Time Analysis of Active Learning -- Coalgebraically in Agda
di: Wißmann, Thorsten
Pubblicazione: (2026)

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

Random Testing of Model Checkers for Timed Automata with Automated Oracle Generation
di: Manini, Andrea, et al.
Pubblicazione: (2025)

A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation
di: Akshay, S, et al.
Pubblicazione: (2023)

Exploiting Assumptions for Effective Monitoring of Real-Time Properties under Partial Observability
di: Cimatti, Alessandro, et al.
Pubblicazione: (2024)

Efficient Runtime Verification of Real-Time Systems under Parametric Communication Delays
di: Fränzle, Martin, et al.
Pubblicazione: (2024)