Semigroups, Presburger formulas, and languages

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

Edwin H. Spanier, Seymour Ginsburg

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 (only showing first 100 items - show all)

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

This page was built for publication: Semigroups, Presburger formulas, and languages