A linear-time algorithm for the orbit problem over cyclic groups

DOI10.1007/S00236-015-0251-0zbMATH Open1347.68186arXiv1411.3164OpenAlexW2099783652MaRDI QIDQ303693FDOQ303693

Authors: Sanming Zhou, Anthony Widjaja Lin 

Publication date: 22 August 2016

Published in: Acta Informatica (Search for Journal in Brave)

Abstract: The orbit problem is at the heart of symmetry reduction methods for model checking concurrent systems. It asks whether two given configurations in a concurrent system (represented as finite strings over some finite alphabet) are in the same orbit with respect to a given finite permutation group (represented by their generators) acting on this set of configurations by permuting indices. It is known that the problem is in general as hard as the graph isomorphism problem, whose precise complexity (whether it is solvable in polynomial-time) is a long-standing open problem. In this paper, we consider the restriction of the orbit problem when the permutation group is cyclic (i.e. generated by a single permutation), an important restriction of the problem. It is known that this subproblem is solvable in polynomial-time. Our main result is a linear-time algorithm for this subproblem.

Full work available at URL: https://arxiv.org/abs/1411.3164

Recommendations

• A linear-time algorithm for the orbit problem over cyclic groups
• On the constructive orbit problem
• The Orbit-Stabilizer Problem for Linear Groups
• Polynomial-time algorithm for the orbit problem
• scientific article; zbMATH DE number 1693448

zbMATH Keywords

bit complexity modellinear algorithmsorbit problemsystem of linear congruence equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Congruences; primitive roots; residue systems (11A07) Finite abelian groups (20K01)

Cites Work

• Introduction to algorithms.
• Title not available (Why is that?)
• Combinatorial matrix classes
• Title not available (Why is that?)
• An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Faster deterministic integer factorization
• Polynomial-time algorithm for the orbit problem
• The Birth of Model Checking
• Title not available (Why is that?)
• A Stirling Encounter with Harmonic Numbers
• Validation of Stochastic Systems
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• On the constructive orbit problem

Cited In (3)

• A linear-time algorithm for the orbit problem over cyclic groups
• The Orbit-Stabilizer Problem for Linear Groups
• On the constructive orbit problem

Uses Software

• OEIS

This page was built for publication: A linear-time algorithm for the orbit problem over cyclic groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q303693)