Constructing an automaton graph representation for stack polygons and bar-graph polygons

Authors

Raymond R. Lapus, De La Salle University, Manila

College

College of Science

Department/Unit

Mathematics and Statistics Department

Document Type

Article

Source Title

DLSU Mathematic Inbox

Issue

Special issue

Publication Date

2009

Abstract

An automaton A is a five-tuple (Σ, A, τ, ι, F) such that Σ is the collection of states; A is the alphabet set; τ: Σ x A → Σ is the transition function defined by τ ( s, a) s', for some s' ∈ Σ; ι ∈ Σ is the initial state; and a non-empty set F ⊆ Σ is the collection of final states. A is pictorially identified with a pictorial representation of a "labeled" directed graph with vertices v ∈ Σ and with an edge (s, t) labeled by a ∈ A if and only if τ(s, a) = t for s, t ∈ Σ and a ∈ A. A word v = v1v2 • • • v_k over the alphabet A is a sequence of letters V_i ∈ A such that τ(ι, v₁) = s₁ only if s_k ∈ F. The collection of all recognized words by A is the language L (A) of A.

Let G (m, n) = [1..m]x[1..m] ⊆ Z² be a grid. A self-avoiding polygon over a G is a sequence of points W = ⁿ_k=₀ such that |_wk-₁ – _wk| = 1 for each k (l ≤ k ≤ n) and _w0 n. = _Wn. The line connecting _wk-l and _Wk is referred as the step _sk in W for k = 1,2,…,n. This paper only considers two subclasses of self-avoiding polygon: the bar-graph polygon and the stack polygons. A "weak" automaton is constructed for each of these class of self-avoiding polygons. Each step from the walk W that formed these polygons are taken from the alphabet A= {d, l, r, u} representing the usual four-directional steps (up, down, right and left) from an arbitrary point in Z². Furthermore, restrictions are imposed on the language of the automat representation for the class of stack polygon so that the words recognized by this automaton represents a walk forming an arbitrary stack polygon. The same procedure is done for the class of bar-graph polygons.

html

Recommended Citation

Lapus, R. R. (2009). Constructing an automaton graph representation for stack polygons and bar-graph polygons. DLSU Mathematic Inbox (Special issue) Retrieved from https://animorepository.dlsu.edu.ph/faculty_research/7818

Disciplines

Mathematics

Note

Abstract only

Keywords

Polygons

Upload File

wf_no