The Parametric Complexity of Lossy Counter Machines
From MaRDI portal
Recommendations
Cites work
- Algorithmic analysis of programs with well quasi-ordered domains.
- Complexity bounds for some finite forms of Kruskal's theorem
- Complexity hierarchies beyond elementary
- Future-Looking Logics on Data Words and Trees
- Hierarchies of number-theoretic functions. I
- History-register automata
- scientific article; zbMATH DE number 1809622 (Why is no real title available?)
- scientific article; zbMATH DE number 3677903 (Why is no real title available?)
- Linearizing well quasi-orders and bounding the length of bad sequences
- Lossy counter machines decidability cheat sheet
- LTL with the freeze quantifier and register automata
- Maximal decidable fragments of Halpern and Shoham's modal logic of intervals
- Multiply-recursive upper bounds with Higman's lemma
- On freeze LTL with ordered attributes
- On the finite containment problem for Petri nets
- Ordering by Divisibility in Abstract Algebras
- Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
- Ordinal recursive bounds for Higman's theorem
- Ordinal recursive complexity of unordered data nets
- Petri nets and large finite sets
- Proofs and computations
- Recursivite et cônes rationnels fermés par intersection
- Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
- Senescent ground tree rewrite systems
- Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
- The complexity of coverability in -Petri nets
- The complexity of decision procedures in relevance logic II
- The Complexity of the Finite Containment Problem for Petri Nets
- The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete
- The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets
- The parametric ordinal-recursive complexity of Post embedding problems
- The power of priority channel systems
- The power of well-structured systems
- The theory of well-quasi-ordering: a frequently discovered concept
- Trace inclusion for one-counter nets revisited
- Undecidable problems in unreliable computations.
- Verifying lossy channel systems has nonprimitive recursive complexity.
- Verifying programs with unreliable channels
- Well-structured transition systems everywhere!
- Zeno, Hercules, and the Hydra: safety metric temporal logic is Ackermann-complete
Cited in
(6)- On the complexity of decision problems for counter machines with applications to coding theory
- Branching in well-structured transition systems (invited talk)
- Bisimulation equivalence of pushdown automata is Ackermann-complete
- On the length of strongly monotone descending chains over \(\mathbb{N}^d\)
- On the width of the Cartesian product of ordinals
- Well-quasi-orderings on word languages
This page was built for publication: The Parametric Complexity of Lossy Counter Machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092331)
