scientific article; zbMATH DE number 3823146

MaRDI QIDQ3668872zbMATH OpenFDO

Authors Thiet-Dung Huynh

Publication date 1982

zbMATH Keywords

accepted languagecomputational complexitydecision problemsinequality problempolynomial hierarchysemilinear setsturing machineuniform word problem

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Word problems, etc. in computability and recursion theory (03D40) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cited in

(17)

• 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
• Analysis of a class of communicating finite state machines
• On reachability equivalence for BPP-nets
• Problems on finite automata and the exponential time hypothesis
• The synthesis of Petri nets from path-automatic specifications
• Characterization and complexity results on jumping finite automata
• On the containment problem for linear sets
• On the structure of linear apex NLC graph grammars
• A Fully Equational Proof of Parikh's Theorem
• Operational state complexity and decidability of jumping finite automata
• Synchronization of Parikh automata
• Geometric decision procedures and the VC dimension of linear arithmetic theories
• On the power of ordering in linear arithmetic theories
• An introduction to the theory of linear integer arithmetic (invited paper)
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete

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 Q3668872)