Imagen de Portada

Stochastic Process Turing Machines

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Wolpert, David, Scharnhorst, Jordan
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Formal Languages and Automata Theory Logic in Computer Science
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
por: Halftermeyer, Pierre
Publicado: (2026)

Non-commutative linear logic fragments with sub-context-free complexity
por: Nishimiya, Yusaku, et al.
Publicado: (2025)

Proceedings Fifteenth International Symposium on Games, Automata, Logics, and Formal Verification
por: Achilleos, Antonis, et al.
Publicado: (2024)

Nets-within-Nets through the Lens of Data Nets
por: Di Cosmo, Francesco, et al.
Publicado: (2025)

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
por: Göller, Stefan, et al.
Publicado: (2023)

On Higher Order Busy Beaver Function
por: Cao, Zining
Publicado: (2025)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
por: Shakiba, Yousef, et al.
Publicado: (2025)

Reachability in Geometrically $d$-Dimensional VASS
por: Fu, Yuxi, et al.
Publicado: (2025)

The Complexity of Nested Reset Counter Systems
por: Balasubramanian, A. R., et al.
Publicado: (2026)

Counting and Sampling Traces in Regular Languages
por: de Colnet, Alexis, et al.
Publicado: (2025)

CMSO-transducing tree-like graph decompositions
por: Campbell, Rutger, et al.
Publicado: (2024)

Weighted basic parallel processes and combinatorial enumeration
por: Clemente, Lorenzo
Publicado: (2024)

A Framework for Universality in Physics, Computer Science, and Beyond
por: Gonda, Tomáš, et al.
Publicado: (2023)

A positional $\mathbfΠ^0_3$-complete objective
por: Casares, Antonio, et al.
Publicado: (2024)

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

Image Reflection on Process Graphs -- A Novel Approach for the Completeness of an Axiomatization of 1-Free Regular Expressions Modulo Bisimilarity
por: Zhang, Yuanrui, et al.
Publicado: (2023)

A Direct Translation from LTL with Past to Deterministic Rabin Automata
por: Azzopardi, Shaun, et al.
Publicado: (2024)

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
por: Daviaud, Laure, et al.
Publicado: (2023)

Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
por: Jecker, Ismaël, et al.
Publicado: (2023)

String Solving with Stabilization and Transducers (Technical Report)
por: Chocholatý, David, et al.
Publicado: (2026)

Robust Probabilistic Bisimilarity for Labelled Markov Chains
por: Fatmi, Syyeda Zainab, et al.
Publicado: (2025)

A cyclic proof system for Guarded Kleene Algebra with Tests (full version)
por: Rooduijn, Jan, et al.
Publicado: (2024)

A proof theory of right-linear (omega-)grammars via cyclic proofs
por: Das, Anupam, et al.
Publicado: (2024)

Function spaces for orbit-finite sets
por: Bojańczyk, Mikołaj, et al.
Publicado: (2024)

An efficient quantifier elimination procedure for Presburger arithmetic
por: Haase, Christoph, et al.
Publicado: (2024)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
por: Barloy, Corentin, et al.
Publicado: (2025)

Positive First-order Logic on Words and Graphs
por: Kuperberg, Denis
Publicado: (2022)

An algebraic theory of ω-regular languages, via μν-expressions
por: Das, Anupam, et al.
Publicado: (2025)

Cyclic system for an algebraic theory of alternating parity automata
por: Das, Anupam, et al.
Publicado: (2025)

Bisimulation for Feller-Dynkin Processes
por: Chen, Linan, et al.
Publicado: (2019)

The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
por: Bhaduri, Purandar
Publicado: (2025)

Studying homing and synchronizing sequences for Timed Finite State Machines with output delays
por: Vinarskii, Evgenii, et al.
Publicado: (2025)

Verifying Quantum Circuits with Level-Synchronized Tree Automata (Technical Report)
por: Abdulla, Parosh Aziz, et al.
Publicado: (2024)

AutoQ 2.0: From Verification of Quantum Circuits to Verification of Quantum Programs (Technical Report)
por: Chen, Yu-Fang, et al.
Publicado: (2024)

Simple grammar bisimilarity, with an application to session type equivalence
por: Poças, Diogo, et al.
Publicado: (2024)

On Dependent Variables in Reactive Synthesis
por: Akshay, S., et al.
Publicado: (2024)

Attractors of Parikh mapping iterations
por: Chunikhin, Alexander
Publicado: (2024)

Invariants for One-Counter Automata with Disequality Tests
por: Chistikov, Dmitry, et al.
Publicado: (2024)

Proceedings Combined 31st International Workshop on Expressiveness in Concurrency and 21st Workshop on Structural Operational Semantics
por: Caltais, Georgiana, et al.
Publicado: (2024)

Logic and Languages of Higher-Dimensional Automata
por: Amrane, Amazigh, et al.
Publicado: (2024)