scientific article
From MaRDI portal
Publication:3668872
zbMath0519.68060MaRDI QIDQ3668872
Publication date: 1982
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitydecision problemspolynomial hierarchysemilinear setsinequality problemuniform word problemturing machineaccepted language
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Word problems, etc. in computability and recursion theory (03D40)
Related Items (14)
The synthesis of Petri nets from path-automatic specifications ⋮ Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ Completeness results for conflict-free vector replacement systems ⋮ Problems on finite automata and the exponential time hypothesis ⋮ On reachability equivalence for BPP-nets ⋮ Synchronization of Parikh automata ⋮ On the structure of linear apex NLC graph grammars ⋮ Operational State Complexity and Decidability of Jumping Finite Automata ⋮ Normal and sinkless Petri nets ⋮ Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete ⋮ Analysis of a class of communicating finite state machines ⋮ A Fully Equational Proof of Parikh's Theorem ⋮ On the Containment Problem for Linear Sets ⋮ Characterization and complexity results on jumping finite automata
This page was built for publication:
