:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Gezer, M. Utkan, Say, A. C. Cem
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity F.1.2; F.1.1; F.4.3
Online Access:	https://arxiv.org/abs/2306.09542
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On some Classes of Reversible 2-head Automata
by: Nagy, Benedek, et al.
Published: (2025)

A LOCAL View of the Polynomial Hierarchy
by: Reiter, Fabian
Published: (2023)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
by: Esparza, Javier, et al.
Published: (2025)

Imperative process algebra and models of computation
by: Middelburg, C. A.
Published: (2022)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
by: Kawałek, Piotr, et al.
Published: (2026)

Turn Complexity of Context-free Languages, Pushdown Automata and One-Counter Automata
by: Pighizzini, Giovanni
Published: (2026)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

A point to set principle for finite-state dimension
by: Mayordomo, Elvira
Published: (2022)

Lexicographic transductions of finite words
by: Filiot, Emmanuel, et al.
Published: (2025)

Identity Testing for Stochastic Languages
by: Agarwal, Smayan, et al.
Published: (2025)

Orbit-finite linear programming
by: Ghosh, Arka, et al.
Published: (2023)

On Some Complexity Results for Even Linear Languages
by: Cojocaru, Liliana
Published: (2024)

Geometric Characterization of Context-Free Intersections via the Inner Segment Dichotomy
by: Silva, Jorge Miguel
Published: (2026)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

On Repetitive Finite Automata with Translucent Words
by: Mráz, František, et al.
Published: (2025)

On the Boolean Closure of Deterministic Top-Down Tree Automata
by: Löding, Christof, et al.
Published: (2024)

On Minimization and Learning of Deterministic $ω$-Automata in the Presence of Don't Care Words
by: Löding, Christof, et al.
Published: (2022)

Recognizing Numbers
by: Gaba, Pranshu, et al.
Published: (2025)

Probabilistic Finite Automaton Emptiness is undecidable
by: Rote, Günter
Published: (2024)

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata
by: Bojańczyk, Mikołaj, et al.
Published: (2021)

Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
by: Rote, Günter
Published: (2024)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

Regular Expressions with Backreferences: Polynomial-Time Matching Techniques
by: Schmid, Markus L.
Published: (2019)

A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings
by: Grabolle, Gustav
Published: (2022)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
by: Bajaj, Divya, et al.
Published: (2026)

Modelling Distributed Applications with Mixed-Choice Stateful Typestates
by: Parrinha, Francisco, et al.
Published: (2026)

Complex Event Recognition with Symbolic Register Transducers: Extended Technical Report
by: Alevizos, Elias, et al.
Published: (2024)

Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices
by: Diekert, Volker, et al.
Published: (2019)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
by: Håstad, Johan, et al.
Published: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
by: de Rezende, Susanna F., et al.
Published: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
by: de Rezende, Susanna F., et al.
Published: (2024)

Supercritical Tradeoffs for Monotone Circuits
by: Göös, Mika, et al.
Published: (2024)

The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory
by: Luo, Wei
Published: (2026)

A Myhill-Nerode Type Characterization of 2detLIN Languages
by: Nagy, Benedek
Published: (2025)

Learning real-time one-counter automata using polynomially many queries
by: Mathew, Prince, et al.
Published: (2024)

Finitely Presentable Higher-Dimensional Automata and the Irrationality of Process Replication
by: Basold, Henning, et al.
Published: (2023)

A simple protocol to automate the executing, scaling, and reconfiguration of Cloud-Native Apps
by: Ambroszkiewicz, Stanislaw, et al.
Published: (2023)