scientific article; zbMATH DE number 4001487

MaRDI QIDQ4727433zbMATH OpenFDO

Authors Dung T. Huynh

Publication date 1986

zbMATH Keywords

inequivalence problempolynomial time hierarchysemilinear sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• On the containment problem for linear sets
• The taming of the semi-linear set
• On the descriptional complexity of operations on semilinear sets
• Learning semilinear sets from examples and via queries
• On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\)

Cited in

(10)

• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• Completeness results for conflict-free vector replacement systems
• Normal and sinkless Petri nets
• On reachability equivalence for BPP-nets
• Equational theories for automata
• Context-free commutative grammars with integer counters and resets
• On the containment problem for linear sets
• A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application
• Operational state complexity and decidability of jumping finite automata
• Geometric decision procedures and the VC dimension of linear arithmetic theories

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4727433)