Home // ICAS 2018, The Fourteenth International Conference on Autonomic and Autonomous Systems // View article

Minimizing LR(1) State Machines is NP-Hard

Authors:
Wuu Yang

Keywords: graph coloring; LR(1) parser; LALR(1) parser; minimize LR(1) state machine; node coloring; NP-hardness; parsing

Abstract:
LR(1) parsing was a focus of extensive research years ago. Though most fundamental mysteries have been resolved, a few remain hidden in the dark corners. The one we bumped into is the minimization of the LR(1) state machines, which we prove is NP-hard. It is the node-coloring problem that is reduced to the minimization puzzle. The reduction makes use of a technique in constructing a context-free grammar from the graph to be colored. The expected LR(1) state machine is derived from the constructed context-free grammar. A minimized LR(1) machine can be used to recover a minimum coloring of the original graph.

Pages: 23 to 28

Copyright: Copyright (c) IARIA, 2018

Publication date: May 20, 2018

Published in: conference

ISSN: 2308-3913

ISBN: 978-1-61208-634-7

Location: Nice, France

Dates: from May 20, 2018 to May 24, 2018