Copertina

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Yamakami, Tomoyuki
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Formal Languages and Automata Theory Symbolic Computation
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
di: Yamakami, Tomoyuki
Pubblicazione: (2023)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
di: Yamakami, Tomoyuki
Pubblicazione: (2024)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
di: Yamakami, Tomoyuki
Pubblicazione: (2024)

Between SC and LOGDCFL: Families of Languages Accepted by Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
di: Yamakami, Tomoyuki
Pubblicazione: (2022)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
di: Yamakami, Tomoyuki
Pubblicazione: (2021)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
di: Yamakami, Tomoyuki
Pubblicazione: (2021)

Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice
di: Yamakami, Tomoyuki
Pubblicazione: (2019)

How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?
di: Yamakami, Tomoyuki
Pubblicazione: (2020)

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

Specializing anti-unification for interaction models composition via gate connections
di: Nguetoum, Joel, et al.
Pubblicazione: (2025)

Complexity of Fungal Automaton Prediction
di: Formenti, Enrico, et al.
Pubblicazione: (2026)

Complexity of Unary Exclusive Nondeterministic Finite Automata
di: Kutrib, Martin, et al.
Pubblicazione: (2024)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
di: Podolskii, Vladimir, et al.
Pubblicazione: (2024)

Algebraic power series and their automatic complexity modulo prime powers
di: Rowland, Eric, et al.
Pubblicazione: (2024)

Review of Automaton Learning Algorithms with Polynomial Complexity -- Completely Solved Examples
di: Haneef, Farah
Pubblicazione: (2024)

Scalable and Approximation-free Symbolic Control for Unknown Euler-Lagrange Systems
di: Das, Ratnangshu, et al.
Pubblicazione: (2025)

CFLOBDDs: Context-Free-Language Ordered Binary Decision Diagrams
di: Sistla, Meghana, et al.
Pubblicazione: (2022)

Computing Sound Lower and Upper Bounds on Hamilton-Jacobi Reach-Avoid Value Functions
di: Tabbara, Ihab, et al.
Pubblicazione: (2025)

Trading Determinism for Noncommutativity in Edmonds' Problem
di: Arvind, V., et al.
Pubblicazione: (2024)

Tracer: A Tool for Race Detection in Software Defined Network Models
di: Caltais, Georgiana, et al.
Pubblicazione: (2024)

Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata
di: Kiefer, Stefan, et al.
Pubblicazione: (2025)

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

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

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

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

Regular Expressions with Backreferences and Lookaheads Capture NLOG
di: Uezato, Yuya
Pubblicazione: (2024)

Maximal Length Cellular Automata : A Survey
di: Adak, Sumit, et al.
Pubblicazione: (2024)

Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024)
di: Manea, Florin, et al.
Pubblicazione: (2024)

Synthesis of Timeline-Based Planning Strategies Avoiding Determinization
di: Acampora, Renato, et al.
Pubblicazione: (2024)

Proceedings of the 15th International Workshop on Non-Classical Models of Automata and Applications
di: Moreira, Nelma, et al.
Pubblicazione: (2025)

On the complexity of computing Strahler numbers
di: Ganardi, Moses, et al.
Pubblicazione: (2025)

Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
di: Gezer, M. Utkan, et al.
Pubblicazione: (2020)

Visibly Recursive Automata
di: Dubrulle, Kévin, et al.
Pubblicazione: (2026)

Entropy of pebble automata and space complexity
di: Montoya, J. Andres
Pubblicazione: (2026)

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

Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
di: Bozga, Marius, et al.
Pubblicazione: (2026)

Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
di: Chen, Zeyu, et al.
Pubblicazione: (2025)

Embedding arbitrary Boolean circuits into fungal automata with arbitrary update sequences
di: Goles, Eric, et al.
Pubblicazione: (2026)

Classification of Local Optimization Problems in Directed Cycles
di: Boudier, Thomas, et al.
Pubblicazione: (2026)

FORM: Learning Expressive and Transferable First-Order Logic Reward Machines
di: Ardon, Leo, et al.
Pubblicazione: (2024)