Cover Image

TuringQ: Benchmarking AI Comprehension in Theory of Computation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zahraei, Pardis Sadat, Asgari, Ehsaneddin
Format:	Preprint
Published:	2024
Subjects:	Computation and Language Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Self-Replicating Mechanical Universal Turing Machine
by: Lano, Ralph P.
Published: (2024)

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

Benchmarking Testing in Automated Theorem Proving
by: Kim, Jongyoon, et al.
Published: (2026)

Cayley Automatic Groups and Numerical Characteristics of Turing Transducers
by: Berdinsky, Dmitry
Published: (2016)

An Automata-Based Method to Formalize Psychological Theories -- The Case Study of Lazarus and Folkman's Stress Theory
by: Finkel, Alain, et al.
Published: (2025)

Computational Complexity of Alignments
by: Schwanen, Christopher T., et al.
Published: (2026)

Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks
by: Shelat, Shlok, et al.
Published: (2026)

Standard Automata Theory and Process Algebra
by: Yodaiken, Victor
Published: (2022)

Computational Model for Parsing Expression Grammars
by: Rubtsov, Alexander, et al.
Published: (2024)

Large Language Models and the Extended Church-Turing Thesis
by: Wiedermann, Jiří, et al.
Published: (2024)

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

Computing measures of weak-MSO definable sets of trees
by: Niwiński, Damian, et al.
Published: (2024)

Undecidability of the Emptiness Problem for Weak Models of Distributed Computing
by: Principato, Flavio T., et al.
Published: (2025)

On the Complexity of Computing the Co-lexicographic Width of a Regular Language
by: Becker, Ruben, et al.
Published: (2024)

Stochastic Process Turing Machines
by: Wolpert, David, et al.
Published: (2024)

Consistent Autoformalization for Constructing Mathematical Libraries
by: Zhang, Lan, et al.
Published: (2024)

Directed Regular and Context-Free Languages
by: Ganardi, Moses, et al.
Published: (2024)

A Bionic Natural Language Parser Equivalent to a Pushdown Automaton
by: Wei, Zhenghao, et al.
Published: (2024)

Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length
by: Lan, Nur, et al.
Published: (2024)

Automata-based constraints for language model decoding
by: Koo, Terry, et al.
Published: (2024)

On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
by: Nowak, Franz, et al.
Published: (2024)

Tokenization as Finite-State Transduction
by: Cognetta, Marco, et al.
Published: (2024)

Autoformalization in the Wild: Assessing LLMs on Real-World Mathematical Definitions
by: Zhang, Lan, et al.
Published: (2025)

LangSAT: A Novel Framework Combining NLP and Reinforcement Learning for SAT Solving
by: Pan, Muyu, et al.
Published: (2025)

Knee-Deep in C-RASP: A Transformer Depth Hierarchy
by: Yang, Andy, et al.
Published: (2025)

Comparing Spoken Languages using Paninian System of Sounds and Finite State Machines
by: Prabhu, Shreekanth M, et al.
Published: (2023)

Recursive numeral systems are highly regular and easy to process
by: Prasertsom, Ponrawee, et al.
Published: (2025)

Transducing Language Models
by: Snæbjarnarson, Vésteinn, et al.
Published: (2026)

Explorability in Pushdown Automata
by: Bedi, Ayaan, et al.
Published: (2025)

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
by: Roop, Partha, et al.
Published: (2026)

Reachability in symmetric VASS
by: Kamiński, Łukasz, et al.
Published: (2025)

Tutorial: $φ$-Transductions in OpenFst via the Gallic Semiring
by: Cognetta, Marco, et al.
Published: (2025)

Cluster automata
by: Kornai, András
Published: (2025)

Prefix Parsing is Just Parsing
by: Pasti, Clemente, et al.
Published: (2026)

A* shortest string decoding for non-idempotent semirings
by: Gorman, Kyle, et al.
Published: (2022)

MASA: LLM-Driven Multi-Agent Systems for Autoformalization
by: Zhang, Lan, et al.
Published: (2025)

Decision Procedure for A Theory of String Sequences
by: Hu, Denghang, et al.
Published: (2025)

Scalable Computation of Inter-Core Bounds Through Exact Abstractions
by: Foughali, Mohammed Aristide, et al.
Published: (2024)

Softmax Transformers are Turing-Complete
by: Jiang, Hongjian, et al.
Published: (2025)

I Am Aligned, But With Whom? MENA Values Benchmark for Evaluating Cultural Alignment and Multilingual Bias in LLMs
by: Zahraei, Pardis Sadat, et al.
Published: (2025)