scientific article; zbMATH DE number 3823146

MaRDI QIDQ3668872zbMATH OpenFDO

Authors Thiet-Dung Huynh

Publication date 1982

zbMATH Keywords

computational complexitypolynomial hierarchysemilinear setsdecision problemsinequality problemuniform word problemturing machineaccepted language

Mathematics Subject Classification ID

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

Cited in

(15)

• On reachability equivalence for BPP-nets
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• Completeness results for conflict-free vector replacement systems
• The synthesis of Petri nets from path-automatic specifications
• On the structure of linear apex NLC graph grammars
• Operational state complexity and decidability of jumping finite automata
• Problems on finite automata and the exponential time hypothesis
• Normal and sinkless Petri nets
• Analysis of a class of communicating finite state machines
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• Characterization and complexity results on jumping finite automata
• Geometric decision procedures and the VC dimension of linear arithmetic theories
• On the containment problem for linear sets
• A Fully Equational Proof of Parikh's Theorem
• Synchronization of Parikh automata

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)