Cover Image

Nondeterministic state complexity of square root

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Onishchenko, Sergey
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

Complexity of Unary Exclusive Nondeterministic Finite Automata
by: Kutrib, Martin, et al.
Published: (2024)

On state complexity for subword-closed languages
by: Guyot, Jérôme
Published: (2024)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
by: Yamakami, Tomoyuki
Published: (2024)

Nondeterministic tree-walking automata are not closed under complementation
by: Martynova, Olga, et al.
Published: (2024)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks
by: Dhayalkar, Sahil Rajesh
Published: (2025)

On the piecewise complexity of words
by: Schnoebelen, Philippe, et al.
Published: (2024)

On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report)
by: Holík, Lukáš, et al.
Published: (2025)

The complexity of separability for semilinear sets and Parikh automata
by: Collins, Elias Rojas, et al.
Published: (2024)

The complexity of reachability problems in strongly connected finite automata
by: Kiefer, Stefan, et al.
Published: (2025)

Exact descriptional complexity of determinization of input-driven pushdown automata
by: Martynova, Olga
Published: (2024)

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

On the transversals of Latin squares generated by nonlinear bipermutive cellular automata
by: Dennunzio, Alberto, et al.
Published: (2026)

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

Soft state reduction of fuzzy automata over residuated lattices
by: Nguyen, Linh Anh, et al.
Published: (2025)

[Draft] High-order estimation-based properties and high-order observers for labeled finite-state automata
by: Zhang, Kuize, et al.
Published: (2024)

Bandwidth of Nondeterministic Finite Automata
by: Cho, Da-Jung, et al.
Published: (2026)

Rauzy dimension and finite-state dimension
by: Becher, Verónica, et al.
Published: (2024)

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)

Forgetting Event Order in Higher-Dimensional Automata
by: Zouari, Safa
Published: (2026)

The Quadratic State Cost of Classical Simulation of One-Way Quantum Finite Automata
by: Chen, Zeyu, et al.
Published: (2026)

Exact Accepting-State Spectrum for Reversal of Permutation Automata
by: German, Samuel
Published: (2026)

Temporal Causal Models as a Model of Computation
by: Gladyshev, Maksim, et al.
Published: (2026)

The Similarity Control Problem with Required Events
by: Wang, Yu, et al.
Published: (2026)

History-Deterministic Büchi Automata are Succinct
by: Casares, Antonio, et al.
Published: (2026)

Algebraic Characterization of FO-definable Languages of Higher-Dimensional Automata
by: Erlich, Enzo, et al.
Published: (2026)

Reversible Weighted Automata over Finite Rings and Monoids with Commuting Idempotents
by: Kostolányi, Peter, et al.
Published: (2026)

Localising Stochasticity in Weighted Automata
by: Agarwal, Smayan, et al.
Published: (2026)

A quadratic lower bound for 2DFAs against one-way liveness
by: Adeogun, Kehinde, et al.
Published: (2026)

History-Constrained Systems
by: Kuijer, Louwe B., et al.
Published: (2026)

AGDES: Automatic Generation of Dependent Event Sequences
by: Guzman, Alexander Obeid
Published: (2026)

Minimizing Streaming String Transducers: An algebraic approach
by: Benalioua, Yahia Idriss, et al.
Published: (2026)

Forbidden-Context & Ordered Grammar Systems
by: Fernau, Henning, et al.
Published: (2026)

Active Inference of Extended Finite State Machine Models with Registers and Guards
by: Groz, Roland, et al.
Published: (2026)

Distributional Learning of Graph Languages Generated by Fixed-Interface Clause Systems
by: Shoudai, Takayoshi, et al.
Published: (2026)

Shuffles of Context-Free Languages along Regular Trajectories
by: Barloy, Corentin, et al.
Published: (2026)

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

Weighted Automata and Regular Expressions for Financial Systems
by: Droste, Manfred, et al.
Published: (2026)

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