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

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

Authors Sanming Zhou, Anthony Widjaja Lin 

Publication date 22 August 2016

Published in Acta Informatica (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 2204782 (Why is no real title available?)
• A Stirling Encounter with Harmonic Numbers
• 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
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Combinatorial matrix classes
• Faster deterministic integer factorization
• Introduction to algorithms.
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• On the constructive orbit problem
• Polynomial-time algorithm for the orbit problem
• The Birth of Model Checking
• Validation of Stochastic Systems

Cited in

(3)

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

Describes a project that uses

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)