Parallel program schemata
From MaRDI portal
Publication:2540014
DOI10.1016/S0022-0000(69)80011-5zbMath0198.32603OpenAlexW2106001218MaRDI QIDQ2540014
Richard M. Karp, Raymond E. Miller
Publication date: 1969
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(69)80011-5
Related Items
Deterministic function computation with chemical reaction networks, Complexity of certain decision problems about congruential languages, Forward analysis and model checking for trace bounded WSTS, Finite-memory automata, Some decision problems for parallel communicating grammar systems, Concurrent abstract state machines, Concurrent program schemes and their logics, Bounded self-stabilizing Petri nets, Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states, An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems, A note on fine covers and iterable factors of VAS languages, Cause-effect structures, Petri nets, Horn programs, linear logic and vector games, Metric propositional neighborhood logic with an equivalence relation, Mathematical programming approach to the Petri nets reachability problem, Completeness results for conflict-free vector replacement systems, On selective unboundedness of VASS, Problems concerning fairness and temporal logic for conflict-free Petri nets, An operator net model for distributed systems, Serialization of concurrent programs, Recursivite et cônes rationnels fermés par intersection, On formulating simultaneity for studying parallelism and synchronization, Determinacy and maximal parallelism in a structured model of parallel computation, Macro liveness graph and liveness of \(\omega\)-independent unbounded nets, Linear time analysis of properties of conflict-free and general Petri nets, Speed faults in computation by chemical reaction networks, The reachability problem for branching vector addition systems requires doubly-exponential space, The decidability of persistence for vector addition systems, Well-abstracted transition systems: Application to FIFO automata., Blocking a transition in a free choice net and what it tells about its throughput., Vector addition systems and regular languages, Persistence of vector replacement systems is decidable, Step coverability algorithms for communicating systems, Synchronous to asynchronous transformation of polyautomata, On the reachability problem for 5-dimensional vector addition systems, Nondecreasing subsequences of t-sequences, Petri nets and regular languages, Some behavioural aspects of net theory, Checking system boundedness using ordinary differential equations, Reduction and covering of infinite reachability trees, On the decision problem for MELL, Algebraic structure of some stochastic discrete event systems, with applications, Extensional Petri net, The complexity of problems involving structurally bounded and conservative Petri nets, A unified approach for deciding the existence of certain petri net paths, Fine covers of a VAS language, Verification of membrane systems with delays via Petri nets with delays, Undecidability of bisimilarity for Petri nets and some related problems, Finite automata on directed graphs, The context-freeness of the languages associated with vector addition systems is decidable, A structure to decide reachability in Petri nets, Testing for unboundedness of fifo channels, Chip-firing games on directed graphs, Normal and sinkless Petri nets, A well-structured framework for analysing Petri net extensions, Proving assertions about parallel programs, A decidability theorem for a class of vector-addition systems, Boundedness analysis for open chemical reaction networks with mass-action kinetics, A note on transition systems, A useful device for showing the solvability of some decision problems, Completeness results for the equivalence of recursive schemas, Finite automata with multiplication, Reachability trees for high-level Petri nets, Some decision problems related to the reachability problem for Petri nets, Commutative grammars, Computation sequence sets, On-the-fly diagnosability analysis of bounded and unbounded labeled Petri nets using verifier nets, Intercalation lemmas for tree transducer languages, The equality problem for vector addition systems is undecidable, Complexity of some problems in Petri nets, Decidable problems on the strong connectivity of Petri net reachability sets, Correctness of parallel programs: The Church-Rosser approach, On reduction of asynchronous systems, The covering and boundedness problems for vector addition systems, Functional behavior in data spaces, (A-)synchronous (non)-deterministic cell spaces simulating each other, The allocation problem in hardware design, Distributed semantics for the \(\pi \)-calculus based on Petri nets with inhibitor ARCS, On the finite containment problem for Petri nets, A multiparameter analysis of the boundedness problem for vector addition systems, Boundedness, empty channel detection, and synchronization for communicating finite automata, On the enlargement of the class of regular languages by the shuffle closure, Projections of vector addition system reachability sets are semilinear, Computation with finite stochastic chemical reaction networks, Decidability problems in grammar systems, Three measures for synchronic dependence in Petri nets, Homomorphisms between models of parallel computation, Determinism in parallel systems, On self-modifying programs, An approach to automating the verification of compact parallel coordination programs. I, The residue of vector sets with applications to decidability problems in Petri nets, Towards a hierarchy of nets, An introduction to FIFO nets - monogeneous nets: a subclass of FIFO nets, Algorithmic analysis of programs with well quasi-ordered domains., Petri nets and large finite sets, Maximal serializability of iterated transactions, Global and local views of state fairness, Petri nets for modeling of dynamic systems -- a survey, Analysis issues in Petri nets with inhibitor arcs, Synchronizing sequences on a class of unbounded systems using synchronized Petri nets, Unnamed Item, REGULAR STATE MACHINES, Ideal Abstractions for Well-Structured Transition Systems, Verification and comparison of transition systems, Alternating two-way AC-tree automata, Reducibilities Among Decision Problems for HNN Groups, Vector Addition Systems and Subsystems of Peano Arithmetic, Model Checking Parameterized Systems, Stratified petri nets, Incremental construction of coverability graphs, Weak Time Petri Nets Strike Back!, Reversible Computation vs. Reversibility in Petri Nets, Une approche quantitative de l'exclusion mutuelle, Unnamed Item, Unnamed Item, Unnamed Item, Data and process resonance. Identifier soundness for models of information systems, Linear logic automata, Correction to: ``Synchronizing sequences on a class of unbounded systems using synchronized Petri nets, Discrete Parameters in Petri Nets, Proving safety properties of infinite state systems by compilation into Presburger arithmetic, On two-way weak counter machines, Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks, Maximal and Minimal Dynamic Petri Net Slicing, Computing with chemical reaction networks: a tutorial, On the Efficient Computation of the Minimal Coverability Set for Petri Nets, Correctness Notions for Petri Nets with Identifiers, Commutative Lambek grammars, Unfolding-based dynamic partial order reduction of asynchronous distributed programs, Unnamed Item, The polynomial complexity of vector addition systems with states, Classifying the computational complexity of problems, Unnamed Item, A note on the emptiness problem for alternating finite-memory automata, Quasi-static scheduling of communicating tasks, The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings, Deciding Fast Termination for Probabilistic VASS with Nondeterminism, Reduced state space representation for unbounded vector state spaces, Data flow analysis of asynchronous systems using infinite abstract domains, Long-Run Average Behavior of Vector Addition Systems with States, Theory of reaction automata: a survey, Strategic reasoning with a bounded number of resources: the quest for tractability, Forward Analysis and Model Checking for Trace Bounded WSTS, Minimal Coverability Set for Petri Nets: Karp and Miller Algorithm with Pruning, Code aware resource management, On the line planning problems of the hub public-transportation networks, Unnamed Item, Equilibrium and termination II: the case of Petri nets, Exhibition of a Structural Bug with Wings, An Assertional Language for the Verification of Systems Parametric in Several Dimensions, Verifying polymer reaction networks using bisimulation, On the Relations between Disjunctive and Linear Logic Programming, Reachability in Timed Counter Systems, Infinite behaviour of Petri nets, Well-structured transition systems everywhere!, The tool TINA – Construction of abstract state spaces for petri nets and time petri nets, Encoding of parallel program schemata by vector addition systems, Unnamed Item, Occam's razor applied to the Petri net coverability problem, On the complexity of resource-bounded logics, Stable leader election in population protocols requires linear time, Unnamed Item, The complexity of decision procedures in relevance logic II, Local time membrane systems and time Petri nets, On the Dynamics of PB Systems with Volatile Membranes, Towards massively parallel computations in algebraic geometry, Unnamed Item, Unnamed Item, Parallel operator schemata over variable arrays and the maximal parallelism problem, Qualitative Analysis of VASS-Induced MDPs, Coverability Trees for Petri Nets with Unordered Data, The Invariance Problem for Matrix Semigroups, Abstract processes and conflicts in place/transition systems, Unbounded-Thread Program Verification using Thread-State Equations, Forward analysis for WSTS, part I: completions, Reachability Problems for Continuous Chemical Reaction Networks, Commodification of accelerations for the Karp and Miller construction, Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States, On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems, Minimal output unstable configurations in chemical reaction networks and deciders, Probability 1 computation with chemical reaction networks, Composable computation in discrete chemical reaction networks, Analyzing Reachability for Some Petri Nets With Fast Growing Markings, Robustness of Expressivity in Chemical Reaction Networks, Stop-transitions of Petri Nets*, Deciding reachability problems in Turing-complete fragments of Mobile Ambients, On program schemata equivalence, A decision procedure using discrete geometry, Introduction to Petri Nets, NEW RESULTS ON COMPUTABILITY OF RECURRENCE EQUATIONS, Livelocks in parallel programs, Unnamed Item, Unnamed Item, Expand, enlarge and check: new algorithms for the coverability problem of WSTS, Undecidable verification problems for programs with unreliable channels, Flat Petri nets (invited talk), Synthesis of (choice-free) reset nets
Cites Work
