Copertina

A quadratic lower bound for 2DFAs against one-way liveness

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Adeogun, Kehinde, Kapoutsis, Christos
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Formal Languages and Automata Theory
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Synchronization of strongly connected partial DFAs and prefix codes
di: Berlinkov, Mikhail V., et al.
Pubblicazione: (2021)

Completely reachable automata: a quadratic decision algorithm and a quadratic upper bound on the reaching threshold
di: Ferens, Robert, et al.
Pubblicazione: (2022)

A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
di: Petrov, Semyon, et al.
Pubblicazione: (2024)

Two-way affine automata can verify every language
di: Chen, Zeyu, et al.
Pubblicazione: (2025)

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

Execution-time opacity problems in one-clock parametric timed automata
di: André, Étienne, et al.
Pubblicazione: (2024)

Maximal 2-dimensional binary words of bounded degree
di: Massé, Alexandre Blondin, et al.
Pubblicazione: (2025)

A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group
di: Zhu, Yinfeng
Pubblicazione: (2024)

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

Regular Grammars for Sets of Graphs of Tree-Width 2
di: Bozga, Marius, et al.
Pubblicazione: (2024)

Equality of cycle lengths in one- and two-dimensional $σ$ automata
di: Vadali, Avi, et al.
Pubblicazione: (2025)

The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently
di: Lehtinen, Karoliina, et al.
Pubblicazione: (2025)

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

A Close Analysis of the Subset Construction
di: Baburin, Ivan, et al.
Pubblicazione: (2024)

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

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

A Variety of Request-Response Specifications
di: Aiba, Daichi, et al.
Pubblicazione: (2025)

A model of actors and grey failures
di: Bocchi, Laura, et al.
Pubblicazione: (2022)

A Formal Approach for Tuning Stochastic Oscillators
di: Ballarini, Paolo, et al.
Pubblicazione: (2024)

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

FocusE: A semantic extension of FocusST
di: Spichkova, Maria
Pubblicazione: (2025)

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

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

A General Information Extraction Framework Based on Formal Languages
di: Schmid, Markus L.
Pubblicazione: (2025)

A Linear-time Simulation of Deterministic $d$-Limited Automata
di: Rubtsov, Alexander
Pubblicazione: (2023)

A pumping-like lemma for languages over infinite alphabets
di: Danieli, Yoav
Pubblicazione: (2025)

A Characterization of Turing Machines that Compute Primitive Recursive Functions
di: Schwartz, Daniel G.
Pubblicazione: (2025)

A Usage-Aware Sequent Calculus for Differential Dynamic Logic
di: Dotzel, Myra, et al.
Pubblicazione: (2023)

A Regular and Complete Notion of Delay for Streaming String Transducers
di: Filiot, Emmanuel, et al.
Pubblicazione: (2022)

A short survey around the pumping lemma for context-free languages
di: Gullà, Gabriele
Pubblicazione: (2024)

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

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
di: Bergsträßer, Pascal, et al.
Pubblicazione: (2024)

iCPS-DL: A Description Language for Autonomic Industrial Cyber-Physical Systems
di: Kouzapas, Dimitrios, et al.
Pubblicazione: (2024)

TARZAN: A Region-Based Library for Forward and Backward Reachability of Timed Automata (Extended Version)
di: Manini, Andrea, et al.
Pubblicazione: (2026)

Frequency Automata: A novel formal model of hybrid systems in combined time and frequency domains
di: Kim, Moon, et al.
Pubblicazione: (2025)

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

GrappaRE -- A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions
di: De Rosa, Mattia, et al.
Pubblicazione: (2025)

From Trees to Tree-Like: Distribution and Synthesis for Asynchronous Automata
di: Lehaut, Mathieu, et al.
Pubblicazione: (2026)

One-clock synthesis problems
di: Lasota, Sławomir, et al.
Pubblicazione: (2026)

Infinite-state Games with Energy Objectives Beyond Counters
di: Sağlam, Irmak, et al.
Pubblicazione: (2026)