\(Q\)-grammars and wall polyominoes (Q1306603): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Set OpenAlex properties.
 
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/bf01608790 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2092841585 / rank
 
Normal rank

Latest revision as of 10:29, 30 July 2024

scientific article
Language Label Description Also known as
English
\(Q\)-grammars and wall polyominoes
scientific article

    Statements

    \(Q\)-grammars and wall polyominoes (English)
    0 references
    0 references
    5 October 1999
    0 references
    A wall polyomino (or bar-graph polygon or solid-on-solid walk) is defined as a vertically convex polyomino in which all columns have their lowest cell at the same level. The upper path of such a polyomino can be bijectively coded with words using letters \(x\), \(y\), \(\overline y\) (corresponding to east, north and south steps). The language of nonempty words coding such polyominoes is algebraic and is generated by an unambiguous grammar. A slightly different grammar corresponds to coding directed positive words. The grammars lead to functional equations for generating functions for the polyominoes. The form of these equations, and some simple singularity computations, are used to prove that the area of wall polyominoes of perimeter \(2n\) has the Airy distribution as a limit law.
    0 references
    asymptotic enumeration
    0 references
    polyomino
    0 references
    words
    0 references
    coding
    0 references
    grammar
    0 references
    generating functions
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references