Cover Image

On Some Complexity Results for Even Linear Languages

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Cojocaru, Liliana
Format:	Preprint
Published:	2024
Subjects:	Formal Languages and Automata Theory Computational Complexity Logic in Computer Science 03D10, 03D15, F.1.1; F.4.1; F.4.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Stratifiable formulae are not context-free
by: Ryan-Smith, Calliope
Published: (2023)

Openness And Partial Adjacency In One Variable TPTL
by: Krishna, Shankara Narayanan, et al.
Published: (2024)

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

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

Determination of the fifth Busy Beaver value
by: The bbchallenge Collaboration, et al.
Published: (2025)

$\mathbb{N}$-polyregular functions arise from well-quasi-orderings
by: Lopez, Aliaume
Published: (2024)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

A Logic For Fresh Labelled Transition Systems
by: Bandukara, Mohamed H, et al.
Published: (2025)

Characterizing NC1 with Typed Monoids
by: Dawar, Anuj, et al.
Published: (2025)

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

On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic
by: Bacik, Piotr, et al.
Published: (2026)

Decision Problems on Copying and Shuffling
by: Halava, Vesa, et al.
Published: (2023)

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

How Concise are Chains of co-Büchi Automata?
by: Ehlers, Rüdiger
Published: (2025)

A Decision Procedure for Probabilistic Kleene Algebra with Angelic Nondeterminism
by: Ong, Shawn, et al.
Published: (2025)

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

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

Exploring the abyss in Kleene's computability theory
by: Sanders, Sam
Published: (2023)

On some computational properties of open sets
by: Normann, Dag, et al.
Published: (2024)

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Punctually Standard and Nonstandard Models of Natural Numbers
by: Bazhenov, Nikolay, et al.
Published: (2026)

Satisfiability of Context-free String Constraints with Subword-ordering and Transducers
by: Aiswarya, C, et al.
Published: (2024)

Introducing Divergence for Infinite Probabilistic Models
by: Finkel, Alain, et al.
Published: (2023)

Loops, Inverse Limits and Non-Determinism
by: Brattka, Vasco
Published: (2025)

Consistent ultrafinitist logic
by: Gajda, Michał J.
Published: (2021)

Weihrauch problems as containers
by: Pradic, Cécilia, et al.
Published: (2025)

Undecidability in Relevant Logic
by: Knudstorp, Søren Brinck
Published: (2026)

Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
by: Anttila, Aleksi, et al.
Published: (2025)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
by: Lopez, Aliaume
Published: (2024)

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

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

Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages
by: Adsul, Bharat, et al.
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)