scientific article; zbMATH DE number 3823146
From MaRDI portal
Publication:3668872
zbMATH Open0519.68060MaRDI QIDQ3668872FDOQ3668872
Publication date: 1982
Title of this publication is not available (Why is that?)
computational complexitypolynomial hierarchysemilinear setsdecision problemsinequality problemuniform word problemturing machineaccepted language
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 the Containment Problem for Linear Sets
- 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
- 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
- Geometric decision procedures and the VC dimension of linear arithmetic theories
- Characterization and complexity results on jumping finite automata
- A Fully Equational Proof of Parikh's Theorem
- Synchronization of Parikh automata
- Operational State Complexity and Decidability of Jumping Finite 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)
