Semigroups, Presburger formulas, and languages

DOI10.2140/pjm.1966.16.285zbMath0143.01602OpenAlexW1964874178MaRDI QIDQ2523032

Publication date: 1966

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/pjm.1966.16.285

zbMATH Keywords

mathematical logic

Related Items

Existence of home states in Petri nets is decidable, A counter abstraction technique for verifying properties of probabilistic swarm systems, Parikh’s Theorem and Descriptional Complexity, The synthesis of Petri nets from path-automatic specifications, Bounded languages described by GF(2)-grammars, Two techniques in the area of the star problem in trace monoids, On two-way FA with monotonic counters and quadratic Diophantine equations, On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension, Alternating two-way AC-tree automata, Model-checking CTL* over flat Presburger counter systems, Computation in networks of passively mobile finite-state sensors, Structural Presburger digit vector automata, Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable, Context-free commutative grammars with integer counters and resets, Bisimulation equivalence and regularity for real-time one-counter automata, Multi-dimensional sets recognizable in all abstract numeration systems, Recent Advances in Population Protocols, Document spanners: from expressive power to decision problems, Automata and processes on multisets of communicating objects, Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata, Temporal Specifications with Accumulative Values, Regular languages and partial commutations, The computational power of simple protocols for self-awareness on graphs, Automaticity of double sequences generated by one-dimensional linear cellular automata, A Note on Decidable Separability by Piecewise Testable Languages, Some lower bounds in parameterized \(\mathrm{AC}^{0}\), The decidability of persistence for vector addition systems, Linear Arithmetic with Stars, The complexity of the equivalence problem for two characterizations of Presburger sets, Persistence of vector replacement systems is decidable, Deciding Structural Liveness of Petri Nets, Tree Automata for Non-linear Arithmetic, Unique decipherability in the monoid of languages: an application of rational relations, Deterministic Two-Dimensional Languages over One-Letter Alphabet, Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups, A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups, Word problems over traces which are solvable in linear time, ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS, Passively mobile communicating machines that use restricted space, Computational models for networks of tiny artifacts: a survey, On bounded linear codes and the commutative equivalence, Fractional Collections with Cardinality Bounds, and Mixed Linear Arithmetic with Stars, Reachability relations of timed pushdown automata, ON STATELESS AUTOMATA AND P SYSTEMS, Automata on Multisets of Communicating Objects, On the commutative equivalence of bounded context-free and regular languages: the code case, On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\), Running time analysis of broadcast consensus protocols, Minimizing cost travel in multimodal transport using advanced relation transitive closure, Multipass automata and group word problems, Logically defined subsets of \(\mathbb{N}{}^ k\), Closure properties of knapsack semilinear groups, Undecidability of bisimilarity for Petri nets and some related problems, Formulas, regular languages and Boolean circuits, FORWARD ANALYSIS OF DYNAMIC NETWORK OF PUSHDOWN SYSTEMS IS EASIER WITHOUT ORDER, Automata for unordered trees, Verification of population protocols, Unnamed Item, Decidability of the star problem in \(A^*\times{}\{ b\}^*\), Sparse and slender subsets of monoids., Mediated population protocols, Leaderless deterministic chemical reaction networks, On two-way nondeterministic finite automata with one reversal-bounded counter, Two iteration theorems for some families of languages, Multitree automata that count, LTL over integer periodicity constraints, Decidability of performance equivalence for basic parallel processes, The algebraic theory of Parikh automata, Decidable problems on the strong connectivity of Petri net reachability sets, Langages algébriques, paires iterantes et transductions rationnelles, Counting productions in context-free derivations, Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG], Presburgerness of predicates regular in two number systems, Towards efficient verification of population protocols, Unique Decipherability in the Monoid of Languages: An Application of Rational Relations, Reflections on tiles (in self-assembly), What's decidable about weighted automata?, Forward Analysis of Dynamic Network of Pushdown Systems Is Easier without Order, Quasi-polynomials, linear Diophantine equations and semi-linear sets, Linear-time temporal logics with Presburger constraints: an overview ★, A characterization of semilinear sets, Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable, AFL with the semilinear property, Robustness of Expressivity in Chemical Reaction Networks, The Parikh counting functions of sparse context-free languages are quasi-polynomials, Automata and rational expressions, The complexity of the word problems for commutative semigroups and polynomial ideals, The convex hull of a regular set of integer vectors is polyhedral and effectively computable, On composition and lookahead delegation of \(e\)-services modeled by automata, Gardens of Eden in the game of life, Efficient automated reasoning about sets and multisets with cardinality constraints, Normal Petri nets, Decision problems among the main subfamilies of rational relations, Decidability of bisimilarity for one-counter processes., The star problem and the finite power property in trace monoids: Reductions beyond C4, Modelization of deterministic rational relations, Distances between languages and reflexivity of relations, The commutative closure of shuffle languages over group languages is regular, Knapsack Problems for Wreath Products, Characterization and complexity results on jumping finite automata, Petri nets, commutative context-free grammars, and basic parallel processes, Unnamed Item, Bounded Regular Sets, Unnamed Item, Bisimulation equivalence is decidable for one-counter processes, Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials, Some trace monoids where both the Star problem and the Finite Power Property Problem are decidable, Logical definability of some rational trace languages, Non-closure under complementation for unambiguous linear grammars, Synchronization of Parikh automata, A Characterization of Semilinear Sets, D-finite multivariate series with arithmetic restrictions on their coefficients, Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks, On the existential arithmetics with addition and bitwise minimum, Hairpin completions and reductions: semilinearity properties, On the Commutative Equivalence of Algebraic Formal Series and Languages, Computing with chemical reaction networks: a tutorial, Commutative Lambek grammars, INTERLEAVING LOGIC AND COUNTING, Unnamed Item, An infinite hierarchy of intersections of context-free languages, Computational Complexity of Atomic Chemical Reaction Networks, Cardinality logics. Part II: Definability in languages based on ‘exactly’, Computing the closure of sets of words under partial commutations, Properties of graphs specified by a regular language, Observations about bounded languages and developmental systems, On the Petri net realization of context-free graphs, MUNCH - Automated Reasoner for Sets and Multisets, Some Results on the Length of Proofs, Unnamed Item, Knapsack in hyperbolic groups, Decision Procedures for Multisets with Cardinality Constraints, Accelerating Interpolation-Based Model-Checking, Acceleration in Convex Data-Flow Analysis, Logic and rational languages of scattered and countable series-parallel posets, Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs., Closure properties of synchronized relations, Reachability in Petri Nets with Inhibitor Arcs, Logical Theory of the Additive Monoid of Subsets of Natural Integers, Unnamed Item, Combining Theories with Shared Set Operations, UNAMBIGUOUS CONSTRAINED AUTOMATA, Decidability of Right One-Way Jumping Finite Automata, A Proof of Parikh’s Theorem via Dickson’s Lemma, Regular Graphs and the Spectra of Two-Variable Logic with Counting