Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Unique decomposition of homogeneous languages and application to isothetic regions
 
research article

Unique decomposition of homogeneous languages and application to isothetic regions

Haucourt, Emmanuel
•
Ninin, Nicolas  
May 1, 2019
Mathematical Structures In Computer Science

A language is said to be homogeneous when all its words have the same length. Homogeneous languages thus form a monoid under concatenation. It becomes freely commutative under the simultaneous actions of every permutation group G(n) on the collection of homogeneous languages of length n is an element of N. One recovers the isothetic regions from (Haucourt 2017, to appear (online since October 2017)) by considering the alphabet of connected subsets of the space vertical bar G vertical bar, viz the geometric realization of a finite graph G. Factoring the geometric model of a conservative program amounts to parallelize it, and there exists an efficient factoring algorithm for isothetic regions. Yet, from the theoretical point of view, one wishes to go beyond the class of conservative programs, which implies relaxing the finiteness hypothesis on the graph G. Provided that the collections of n-dimensional isothetic regions over G (denoted by R-n vertical bar G vertical bar) are co -unital distributive lattices, the prime decomposition of isothetic regions is given by an algorithm which is, unfortunately, very inefficient. Nevertheless, if the collections R-n vertical bar G vertical bar satisfy the stronger property of being Boolean algebras, then the efficient factoring algorithm is available again. We relate the algebraic properties of the collections R-n vertical bar G vertical bar to the geometric properties of the space I GI. On the way, the algebraic structure R-n vertical bar G vertical bar is proven to be the universal tensor product, in the category of semilattices with zero, of n copies of the algebraic structure R-1 vertical bar G vertical bar.

  • Details
  • Metrics
Type
research article
DOI
10.1017/S0960129518000294
Web of Science ID

WOS:000461759800003

Author(s)
Haucourt, Emmanuel
Ninin, Nicolas  
Date Issued

2019-05-01

Published in
Mathematical Structures In Computer Science
Volume

29

Issue

5

Start page

681

End page

730

Subjects

Computer Science, Theory & Methods

•

Computer Science

•

tensor product

•

geometry

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
UPHESS  
Available on Infoscience
June 18, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/157033
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés