Imagen de Portada

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Lin, Tianrong
Formato:	Preprint
Publicado:	2021
Materias:	Computational Complexity Formal Languages and Automata Theory 68Q15, 68Q17
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Resolution of The Linear-Bounded Automata Question
por: Lin, Tianrong
Publicado: (2021)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
por: Lin, Tianrong
Publicado: (2024)

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

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

Weighted Automata and Logics Meet Computational Complexity
por: Kostolányi, Peter
Publicado: (2023)

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

Languages given by Finite Automata over the Unary Alphabet
por: Czerwiński, Wojciech, et al.
Publicado: (2023)

The Separation of $NP$ and $PSPACE$
por: Lin, Tianrong
Publicado: (2021)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
por: Lin, Tianrong
Publicado: (2023)

Semidirect Product Decompositions for Periodic Regular Languages
por: Inoue, Yusuke, et al.
Publicado: (2024)

The Polynomial Hierarchy does not collapse
por: Czerwinski, Reiner
Publicado: (2024)

A generalization of Deterministic Finite Automata related to discharging
por: Campbell, John M.
Publicado: (2025)

Mostowski Index via extended register games
por: Idir, Olivier, et al.
Publicado: (2024)

Classically Time-Controlled Quantum Automata: Definition and Properties
por: Díaz-Caro, Alejandro, et al.
Publicado: (2018)

On A. V. Anisimov's problem for finding a polynomial algorithm checking inclusion of context-free languages in group languages
por: Yordzhev, Krasimir
Publicado: (2026)

A hierarchy of reversible finite automata
por: Radionova, Maria, et al.
Publicado: (2024)

On Computational Completeness of Semi-Conditional Matrix Grammars
por: Fernau, Henning, et al.
Publicado: (2024)

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

An $L^{\#}$ Based Algorithm for Active Learning of Minimal Separating Automata
por: Laumen, Jasper, et al.
Publicado: (2026)

From regular expressions to deterministic finite automata: $2^{\frac{n}{2}+\sqrt{n}(\log n)^{Θ(1)}}$ states are necessary and sufficient
por: Martynova, Olga, et al.
Publicado: (2025)

Bounded Languages Described by GF(2)-grammars
por: Makarov, Vladislav
Publicado: (2019)

Linear equations and recursively enumerable sets
por: Honkala, Juha
Publicado: (2024)

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

Around Don's conjecture for binary completely reachable automata
por: Zhu, Yinfeng
Publicado: (2024)

Don's conjecture for binary completely reachable automata: an approach and its limitations
por: Casas, David, et al.
Publicado: (2023)

The Algebra of Nondeterministic Finite Automata
por: Gorrieri, Roberto
Publicado: (2023)

On Quantum Context-Free Grammars
por: Aruja, Merina, et al.
Publicado: (2025)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
por: Cho, Da-Jung, et al.
Publicado: (2025)

From Historical Puzzles to Grammatical Constraints: Circular Partitions, Generalized Run-Length Encodings, and Polynomial-Time Decidability
por: Khormali, Omid, et al.
Publicado: (2026)

Polynomial Identity Testing via Evaluation of Rational Functions
por: Hu, Ivan, et al.
Publicado: (2022)

Deterministic Suffix-reading Automata
por: Keerthan, R, et al.
Publicado: (2025)

Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
por: Guillon, Bruno, et al.
Publicado: (2025)

Weakly-unambiguous Parikh automata and their link to holonomic series
por: Bostan, Alin, et al.
Publicado: (2025)

Probabilistic automatic complexity of finite strings
por: Gill, Kenneth
Publicado: (2024)

Further results on generalized cellular automata
por: Castillo-Ramirez, Alonso, et al.
Publicado: (2023)

Context-Free Trees
por: Wächter, Jan Philipp
Publicado: (2026)

The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory
por: Peyrichou, Romain
Publicado: (2026)

Cone-Induced Observation Congruences for Vector-Valued Quantitative Languages
por: Alpay, Faruk, et al.
Publicado: (2026)

Illustrating Finite Automata with Grail+ and TikZ
por: May, Alastair, et al.
Publicado: (2024)

Normal forms in Virus Machines
por: Ramírez-de-Arellano, A., et al.
Publicado: (2024)