Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Adeogun, Kehinde, Kapoutsis, Christos
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

FocusE: A semantic extension of FocusST
by: Spichkova, Maria
Published: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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