Class: RLSM::Monoid

Inherits:
Object
  • Object
show all
Defined in:
lib/rlsm/monoid.rb

Overview

Implements the mathematical idea of a finite monoid.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(table, validate = true) ⇒ Monoid

Creates a new Monoid from the given table. The table is interpreted as follows:

  • Case 1: Table is an Array.

    It is assumed, that the array is flat and that every entry is an entry in the transition table. The neutral element must be described in the first row and column.

  • Case 2: Table is a String.

    The string will be parsed into a flat Array. If commas are present, the String will be splitted at these, otherwise it will be splitted at each character. Whitespaces will be ignored or threted as commas. After parsing, the resulting array will be treated as in case 1.

Examples:

Some different ways to create a Monoid

RLSM::Monoid.new [0,1,1,1]
RLSM::Monoid.new "0110"
RLSM::Monoid.new "01 10"
RLSM::Monoid.new "0,1,1,0"
RLSM::Monoid.new "0,1 1,0"

Parameters:

  • table (Array, String) —

    The transition table of the monoid, either as a flat Array or a string.

  • validate (Boolean) (defaults to: true) —

    If true, the given table will be validated.

Raises:

  • (RLSM::Error) —

    If validate is true and the given table isn’t associative or has no neutral element or the neutral element isn’t in the first row and column.



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/rlsm/monoid.rb', line 121

def initialize(table, validate = true)
  @table = parse(table)
  @order = Math::sqrt(@table.size).to_i
  @elements = @table[0,@order].clone
  @internal = {}
  @elements.each_with_index { |x,i| @internal[x] = i }
  @table.map! { |x| @internal[x] }

  if validate
    if @order == 0
      raise RLSM::Error, "No elements given."
    end
    
    unless @table.size == @order**2
      raise RLSM::Error, "Binary operation must be quadratic."
    end

    unless @table.uniq.size == @order
      raise RLSM::Error, "Number of different elements is wrong."
    end

    enforce_identity_position(@table, @order)

    nat = non_associative_triple
    unless nat.nil?
      err_str = "(#{nat[0]}#{nat[0]})#{nat[0]} != #{nat[0]}(#{nat[1]}#{nat[2]})"
      raise RLSM::Error, "Associativity required, but #{err_str}."
    end
  end
end

Instance Attribute Details

#elements ⇒ Object (readonly)

The elements of the monoid.



81
82
83
 
# File 'lib/rlsm/monoid.rb', line 81

def elements
  @elements
end

#order ⇒ Object (readonly)

The order of the monoid.



84
85
86
 
# File 'lib/rlsm/monoid.rb', line 84

def order
  @order
end

#table ⇒ Object (readonly)

The transition table of the monoid.



87
88
89
 
# File 'lib/rlsm/monoid.rb', line 87

def table
  @table
end

Class Method Details

.[](table) ⇒ Object

Creates a new monoid.

See Also:



52
53
54
 
# File 'lib/rlsm/monoid.rb', line 52

def [](table)
  new(table)
end

.each(order) {|monoid| ... } ⇒ Object

Iterates over each monoid of the given order.

Parameters:

  • order (Integer) —

    Specifies over which monoids the method iterates.

Yields:

  • (monoid) —

    A monoid of the given order.

Raises:

  • (RLSM::Error) —

    The given parameter must be greater than zero.



20
21
22
 
# File 'lib/rlsm/monoid.rb', line 20

def each(order)
  each_table(order) { |table| yield new(table,false) }
end

.each_table(order) {|table| ... } ⇒ Object

Iterates over each transition table of a monoid of the given order.

Parameters:

  • order (Integer) —

    Specifies over which monoids the method iterates.

Yields:

  • (table) —

    An array describing the transition table of a monoid.

Raises:

  • (RLSM::Error) —

    The given parameter must be greater than zero.



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/rlsm/monoid.rb', line 31

def each_table(order)
  raise RLSM::Error, "Given order must be > 0" if order <= 0

  if order == 1  #trivial case
    yield [0]
    return
  end
  
  #calculate the permutations once
  permutations = 
    RLSM::ArrayExt::permutations((1...order).to_a).map { |p| p.unshift 0 }

  each_diagonal(order,permutations) do |diagonal|
    each_with_diagonal(diagonal,permutations) do |table|
      yield table
    end
  end
end

.from_dfa(dfa) ⇒ Monoid

Creates the syntactic monoid to the given regular language.

Parameters:

  • dfa (String) —

    a deterministic finite automaton

Returns:

  • (Monoid) —

    the syntactic monoid of the given regular language.

Raises:

  • (RLSM::Error) —

    if given string isn’t a valid DFA description.



74
75
76
 
# File 'lib/rlsm/monoid.rb', line 74

def from_dfa(dfa)
  RLSM::DFA[dfa].to_monoid
end

.from_regexp(regexp) ⇒ Monoid

Creates the syntactic monoid to the given regular language.

Parameters:

  • regexp (String) —

    a regular expression.

Returns:

  • (Monoid) —

    the syntactic monoid of the given regular language.

Raises:

  • (RLSM::Error) —

    if given string isn’t a valid regexp.



63
64
65
 
# File 'lib/rlsm/monoid.rb', line 63

def from_regexp(regexp)
  RLSM::RegExp[regexp].to_monoid
end

Instance Method Details

#<(other) ⇒ nil, Boolean

Checks if this monoid is a proper submonoid (i.e. not equal) of the other one.

Parameters:

  • other (Monoid) —

    Righthand side of the inequality test.

Returns:

  • (nil) —

    if other isn’t a monoid.

  • (Boolean) —

    the result of the inequality test.



235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
 
# File 'lib/rlsm/monoid.rb', line 235

def <(other)
  return nil unless RLSM::Monoid === other
  return false if @order >= other.order

  @elements.each do |e1|
    @elements.each do |e2|
      begin
        return false if self[e1,e2] != other[e1,e2]
      rescue RLSM::Error
        return false
      end
    end
  end

  true
end

#<=(other) ⇒ nil, Boolean

Checks if this monoid is a submonoid of the other one.

Parameters:

  • other (Monoid) —

    Righthand side of the inequality test.

Returns:

  • (nil) —

    if other isn’t a monoid.

  • (Boolean) —

    the result of the inequality test.



258
259
260
 
# File 'lib/rlsm/monoid.rb', line 258

def <=(other)
  (self == other) || (self < other)
end

#==(other) ⇒ nil, Boolean

Tests for monoid equality. Two monoids are equal if the have the same set of elements and the same transition table.

Parameters:

  • other (Monoid) —

    The righthand side of the equality test.

Returns:

  • (nil) —

    if other isn’t a monoid.

  • (Boolean) —

    the result of the equality check.



221
222
223
224
225
226
 
# File 'lib/rlsm/monoid.rb', line 221

def ==(other)
  return nil unless RLSM::Monoid === other

  @table == other.table and
    @elements == other.elements
end

#=~(other) ⇒ Object

See Also:



285
286
287
 
# File 'lib/rlsm/monoid.rb', line 285

def =~(other)
  isomorph?(other)
end

#>(other) ⇒ nil, Boolean

Checks if the other monoid is a proper submonoid (i.e. not equal) of this one.

Parameters:

  • other (Monoid) —

    Righthand side of the inequality test.

Returns:

  • (nil) —

    if other isn’t a monoid.

  • (Boolean) —

    the result of the inequality test.



269
270
271
 
# File 'lib/rlsm/monoid.rb', line 269

def >(other)
  other < self
end

#>=(other) ⇒ nil, Boolean

Checks if the other monoid is a submonoid of this one.

Parameters:

  • other (Monoid) —

    Righthand side of the inequality test.

Returns:

  • (nil) —

    if other isn’t a monoid.

  • (Boolean) —

    the result of the inequality test.



279
280
281
282
 
# File 'lib/rlsm/monoid.rb', line 279

def >=(other)
  other <= self
  endy
end

#[](*args) ⇒ Object

Calculates the product of the given elements.

Returns:

  • The result of the operation

Raises:

  • (RLSM::Error) —

    If at least one of the given elements isn’t a element of the monoid or too few elements are given.



171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/rlsm/monoid.rb', line 171

def [](*args)
  case args.size
  when 0,1
    raise RLSM::Error, "At least two elements must be provided."
  when 2
    begin
      @elements[ @table[ @order*@internal[args[0]] + @internal[args[1]] ] ]
    rescue
      raise RLSM::Error, "Given arguments aren't monoid elements."
    end
  else
    args[0,2] = self[ *args[0,2] ]
    self[*args]
  end
end

#all_disjunctive_subsets ⇒ Array

Calculate all disjunctive subsets.

Returns:

  • (Array) —

    all disjunctive subsets.



771
772
773
 
# File 'lib/rlsm/monoid.rb', line 771

def all_disjunctive_subsets
  RLSM::ArrayExt::powerset(@elements).select { |s| subset_disjunctive? s }
end

#antiisomorph?(other) ⇒ nil, Boolean

Checks if this monoid is antiisomorph to the other one.

Parameters:

  • other (Monoid) —

    Righthand side of the isomorphism check.

Returns:

  • (nil) —

    if other isn’t a monoid.

  • (Boolean) —

    the result of the antiisomorphism check.



308
309
310
311
312
313
314
 
# File 'lib/rlsm/monoid.rb', line 308

def antiisomorph?(other)
  return nil unless RLSM::Monoid === other

  antiisomorphisms(other) { return true }

  false
end

#antiisomorphisms(other) {|isomorphism| ... } ⇒ Object

Iterates over all antiisomorphisms form this monoid to the other.

Yields:

  • (isomorphism) —

    An antiisomorphism from this monoid to the other.



944
945
946
947
948
949
950
951
952
953
954
955
956
 
# File 'lib/rlsm/monoid.rb', line 944

def antiisomorphisms(other)
  return [] if @order != other.order

  RLSM::ArrayExt::permutations(other.elements).map do |perm| 
    map = Hash[*@elements.zip(perm).flatten]

    if @elements.all? { |x| @elements.all? { |y|
          map[self[x,y]] == other[map[y],map[x]]
        } }
      yield map
    end
  end
end

#aperiodic? ⇒ Boolean

Checks if the monoid is aperiodic (i.e. H-trivial).

Returns:

  • (Boolean) —

    Result of the check.

See Also:



734
735
736
 
# File 'lib/rlsm/monoid.rb', line 734

def aperiodic?
  h_trivial?
end

#commutative? ⇒ Boolean

Checks if the monoid is commutative.

Returns:

  • (Boolean) —

    Result of the check.



557
558
559
 
# File 'lib/rlsm/monoid.rb', line 557

def commutative?
  is_commutative
end

#d_class(element) ⇒ Array

Calculates the D-class of an element. Synonym for j_class (J and D relation are the same for a finite monoid).

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Array) —

    D-class of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



623
624
625
 
# File 'lib/rlsm/monoid.rb', line 623

def d_class(element)
  j_class(element)
end

#d_classes ⇒ Array

Calculates all D-classes of the monoid.

Returns:

  • (Array) —

    List of all D-classes.



690
691
692
 
# File 'lib/rlsm/monoid.rb', line 690

def d_classes
  j_classes
end

#d_trivial? ⇒ Boolean

Checks if all D-classes of the monoid are singleton sets.

Returns:

  • (Boolean) —

    Result of the check.



725
726
727
 
# File 'lib/rlsm/monoid.rb', line 725

def d_trivial?
  @elements.all? { |el| d_class(el).size == 1 }
end

#disjunctive_subset ⇒ nil, Array

Calculate a disjunctive subset if one exists.

Returns:

  • (nil) —

    if no disjunctive subset exists.

  • (Array) —

    a disjunctive subset.



764
765
766
 
# File 'lib/rlsm/monoid.rb', line 764

def disjunctive_subset
  RLSM::ArrayExt::powerset(@elements).find { |s| subset_disjunctive? s }
end

#element_sorter ⇒ Proc

The order in the transition table is the natural order for the elements.

Returns:

  • (Proc) —

    As argument for the sort method, elements will be compared by their indices rather than by their names.



881
882
883
 
# File 'lib/rlsm/monoid.rb', line 881

def element_sorter
  Proc.new { |el1,el2| @elements.index(el1) <=> @elements.index(el2)}
end

#generated_set(set) ⇒ Array

Calculates the set of elements which will be generated by the given set.

Parameters:

  • set (Array) —

    The elements which act as generators

Returns:

  • (Array) —

    the generated set.

Raises:

  • (RLSM::Error) —

    if one of the elements isn’t a monoid element.

See Also:

  • #get_submonoid.


325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
 
# File 'lib/rlsm/monoid.rb', line 325

def generated_set(set)
  gen_set = set | @elements[0,1]
  
  unfinished = true
  
  while unfinished
    unfinished = false

    gen_set.each do |el1|
      gen_set.each do |el2|
        element = self[el1,el2]
        unless gen_set.include? element
          gen_set << element
          unfinished = true
        end
      end
    end
  end
    
  gen_set.sort(&element_sorter)
end

#generating_subset ⇒ Array

Finds the smallest set which generates the whole monoid (smallest in the sense of cardinality of the set).

Returns:

  • (Array) —

    A set of elements which generates the whole monoid.



386
387
388
 
# File 'lib/rlsm/monoid.rb', line 386

def generating_subset
  sorted_subsets.find { |set| generated_set(set).size == @order }
end

#get_submonoid(set) ⇒ Monoid

Calculates the set of elements which will be generated by the given set.

Parameters:

  • set (Array) —

    The elements which act as generators

Returns:

  • (Monoid) —

    the monoid generated by the given set.

Raises:

  • (RLSM::Error) —

    if one of the elements isn’t a monoid element.

See Also:

  • #get_generated_set.


356
357
358
359
360
 
# File 'lib/rlsm/monoid.rb', line 356

def get_submonoid(set)
  elements = generated_set(set)

  set_to_monoid(elements)
end

#get_submonoid_candidates ⇒ Array

Calculates a list of sets of elements which form a submonoid. Sorts the result.

Returns:

  • (Array) —

    List of sets of elements which form a submonoid.



913
914
915
916
917
918
919
920
921
922
 
# File 'lib/rlsm/monoid.rb', line 913

def get_submonoid_candidates
  submons =  []
  
  RLSM::ArrayExt::powerset(@elements).each do |set|
    candidate = generated_set(set)
    submons << candidate unless submons.include? candidate
  end

  submons.sort(&subset_sorter)
end

#group? ⇒ Boolean

Checks if the monoid is a group.

Returns:

  • (Boolean) —

    Result of the check.



550
551
552
 
# File 'lib/rlsm/monoid.rb', line 550

def group?
  idempotents.size == 1
end

#h_class(element) ⇒ Array

Calculates the H-class of an element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Array) —

    H-class of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



611
612
613
 
# File 'lib/rlsm/monoid.rb', line 611

def h_class(element)
  l_class(element) & r_class(element)
end

#h_classes ⇒ Array

Calculates all H-classes of the monoid.

Returns:

  • (Array) —

    List of all H-classes.



675
676
677
678
679
680
681
682
683
684
685
 
# File 'lib/rlsm/monoid.rb', line 675

def h_classes
  not_tested = @elements.dup
  classes = []
  
  until not_tested.empty?
    classes << h_class(not_tested.first)
    not_tested = not_tested.reject { |el| classes.last.include? el }
  end
  
  classes.sort(&subset_sorter)
end

#h_trivial? ⇒ Boolean

Checks if all H-classes of the monoid are singleton sets.

Returns:

  • (Boolean) —

    Result of the check.



718
719
720
 
# File 'lib/rlsm/monoid.rb', line 718

def h_trivial?
  @elements.all? { |el| h_class(el).size == 1 }
end

#ideal(element) ⇒ Array

Calculates the principal (twosided) ideal of the given element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Array) —

    Principle ideal of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



445
446
447
448
449
450
451
452
453
454
 
# File 'lib/rlsm/monoid.rb', line 445

def ideal(element)
  result = []
  @elements.each do |el1|
    @elements.each do |el2|
      result << self[el1,element,el2]
    end
  end

  result.uniq.sort(&element_sorter)
end

#idempotent? ⇒ Boolean #idempotent?(element) ⇒ Boolean

Checks if the monoid is idempotent (i.e. all elements are idempotent).

Checks if given element is idempotent.

Returns:

  • (Boolean) —

    result of the check



397
398
399
400
401
402
403
 
# File 'lib/rlsm/monoid.rb', line 397

def idempotent?(element = nil)
  if element
    self[element,element] == element
  else
    @elements.all? { |el| idempotent?(el) }
  end
end

#idempotents ⇒ Array

Calculates all idempotent elements of the monoid.

Returns:

  • (Array) —

    the idempotent elements of the monoid.



543
544
545
 
# File 'lib/rlsm/monoid.rb', line 543

def idempotents
  @elements.select { |el| idempotent?(el) }
end

#identity ⇒ Object

The neutral element of the monoid.

Returns:

  • neutral element of the monoid.



459
460
461
 
# File 'lib/rlsm/monoid.rb', line 459

def identity
  @elements.first
end

#identity?(element) ⇒ Boolean

Checks if given element is the neutral element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Boolean) —

    Result of the check.



468
469
470
 
# File 'lib/rlsm/monoid.rb', line 468

def identity?(element)
  element == identity
end

#inspect ⇒ String

Transforms monoid into a string for debug purposes.

Returns:

  • (String) —

    The string representation of the monoid.



210
211
212
 
# File 'lib/rlsm/monoid.rb', line 210

def inspect
  "<#{self.class}: #{to_s}>"
end

#inverse? ⇒ Boolean

Checks if the monoid is inverse.

Returns:

  • (Boolean) —

    Result of the check.



857
858
859
860
 
# File 'lib/rlsm/monoid.rb', line 857

def inverse?
  regular? and
    idempotents.all? { |x| idempotents.all? { |y| self[x,y] == self[y,x] } }
end

#isomorph?(other) ⇒ nil, Boolean

Checks if this monoid is isomorph to the other one.

Parameters:

  • other (Monoid) —

    Righthand side of the isomorphism check.

Returns:

  • (nil) —

    if other isn’t a monoid.

  • (Boolean) —

    the result of the isomorphism check.



295
296
297
298
299
300
 
# File 'lib/rlsm/monoid.rb', line 295

def isomorph?(other)
  return nil unless RLSM::Monoid === other
  isomorphisms(other) { return true }

  false
end

#isomorphisms(other) {|isomorphism| ... } ⇒ Object

Iterates over all isomorphisms form this monoid to the other.

Yields:

  • (isomorphism) —

    An isomorphism from this monoid to the other.



927
928
929
930
931
932
933
934
935
936
937
938
939
 
# File 'lib/rlsm/monoid.rb', line 927

def isomorphisms(other)
  return [] if @order != other.order

  RLSM::ArrayExt::permutations(other.elements).map do |perm| 
    map = Hash[*@elements.zip(perm).flatten]

    if @elements.all? { |x| @elements.all? { |y|
          map[self[x,y]] == other[map[x],map[y]]
        } }
      yield map
    end
  end
end

#j_class(element) ⇒ Array

Calculates the J-class of an element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Array) —

    J-class of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



599
600
601
602
 
# File 'lib/rlsm/monoid.rb', line 599

def j_class(element)
  d = ideal(element)
  @elements.select { |el| ideal(el) == d }
end

#j_classes ⇒ Array

Calculates all J-classes of the monoid.

Returns:

  • (Array) —

    List of all J-classes.



660
661
662
663
664
665
666
667
668
669
670
 
# File 'lib/rlsm/monoid.rb', line 660

def j_classes
  not_tested = @elements.dup
  classes = []
  
  until not_tested.empty?
    classes << j_class(not_tested.first)
    not_tested = not_tested.reject { |el| classes.last.include? el }
  end
  
  classes.sort(&subset_sorter)
end

#j_trivial? ⇒ Boolean

Checks if all J-classes of the monoid are singleton sets.

Returns:

  • (Boolean) —

    Result of the check.



711
712
713
 
# File 'lib/rlsm/monoid.rb', line 711

def j_trivial?
  @elements.all? { |el| j_class(el).size == 1 }
end

#l_class(element) ⇒ Array

Calculates the L-class of an element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Array) —

    L-class of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



575
576
577
578
 
# File 'lib/rlsm/monoid.rb', line 575

def l_class(element)
  li = left_ideal(element)
  @elements.select { |el| left_ideal(el) == li }
end

#l_classes ⇒ Array

Calculates all L-classes of the monoid.

Returns:

  • (Array) —

    List of all L-classes.



645
646
647
648
649
650
651
652
653
654
655
 
# File 'lib/rlsm/monoid.rb', line 645

def l_classes
  not_tested = @elements.dup
  classes = []
  
  until not_tested.empty?
    classes << l_class(not_tested.first)
    not_tested = not_tested.reject { |el| classes.last.include? el }
  end
  
  classes.sort(&subset_sorter)
end

#l_trivial? ⇒ Boolean

Checks if all L-classes of the monoid are singleton sets.

Returns:

  • (Boolean) —

    Result of the check.



704
705
706
 
# File 'lib/rlsm/monoid.rb', line 704

def l_trivial?
  @elements.all? { |el| l_class(el).size == 1 }
end

#left_ideal(element) ⇒ Array

Calculates the principal left ideal of the given element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Array) —

    Principle left ideal of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



434
435
436
 
# File 'lib/rlsm/monoid.rb', line 434

def left_ideal(element)
  @elements.map { |el| self[el,element] }.uniq.sort(&element_sorter)
end

#left_zero?(element) ⇒ Boolean

Checks if the given element is a left zero element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Boolean) —

    Result of the check.

Raises:

  • (RLSM::Error) —

    if element isn’t a monoid element



509
510
511
512
 
# File 'lib/rlsm/monoid.rb', line 509

def left_zero?(element)
  return false if @order == 1
  @elements.all? { |x| self[element,x] == element }
end

#left_zeros ⇒ Array

Calculates all left zero elements of the monoid.

Returns:

  • (Array) —

    the left zero elements of the monoid.



536
537
538
 
# File 'lib/rlsm/monoid.rb', line 536

def left_zeros
  @elements.select { |el| left_zero?(el) }
end

#monogenic? ⇒ Boolean

Checks if the monoid is monogenic (i.e. generated by a single element).

Returns:

  • (Boolean) —

    Result of the check.



564
565
566
 
# File 'lib/rlsm/monoid.rb', line 564

def monogenic?
  generating_subset.size == 1
end

#order_of(element) ⇒ Integer

Calculates the order of the monoid.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Integer) —

    Order of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



412
413
414
 
# File 'lib/rlsm/monoid.rb', line 412

def order_of(element)
  generated_set([element]).size
end

#parse(table) ⇒ Array

Parses a transition table description.

Parameters:

  • table (Array, String) —

    the transition table description.

Returns:

  • (Array) —

    The parsed description.



157
158
159
160
161
162
163
164
165
 
# File 'lib/rlsm/monoid.rb', line 157

def parse(table)
  return table if Array === table

  if table.include?(',')
    table.gsub(/\W/,',').squeeze(',').split(',').reject { |x| x.empty? }
  else
    table.gsub(/\W/,'').scan(/./)
  end
end

#proper_submonoids ⇒ Array

Calculates all proper submonoids (i.e. all submonoids without the monoid itself and the trivial one).

Returns:

  • (Array) —

    List with all proper submonoids in it.



374
375
376
377
378
379
380
 
# File 'lib/rlsm/monoid.rb', line 374

def proper_submonoids
  candidates = get_submonoid_candidates.select do |cand| 
    cand.size > 1 and cand.size < @order 
  end

  candidates.map { |set| set_to_monoid(set) }
end

#r_class(element) ⇒ Array

Calculates the R-class of an element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Array) —

    R-class of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



587
588
589
590
 
# File 'lib/rlsm/monoid.rb', line 587

def r_class(element)
  r = right_ideal(element)
  @elements.select { |el| right_ideal(el) == r }
end

#r_classes ⇒ Array

Calculates all R-classes of the monoid.

Returns:

  • (Array) —

    List of all R-classes.



630
631
632
633
634
635
636
637
638
639
640
 
# File 'lib/rlsm/monoid.rb', line 630

def r_classes
  not_tested = @elements.dup
  classes = []
  
  until not_tested.empty?
    classes << r_class(not_tested.first)
    not_tested = not_tested.reject { |el| classes.last.include? el }
  end
  
  classes.sort(&subset_sorter)
end

#r_trivial? ⇒ Boolean

Checks if all R-classes of the monoid are singleton sets.

Returns:

  • (Boolean) —

    Result of the check.



697
698
699
 
# File 'lib/rlsm/monoid.rb', line 697

def r_trivial?
  @elements.all? { |el| r_class(el).size == 1 }
end

#regular? ⇒ Boolean #regular?(a) ⇒ Boolean

Checks if the monoid is regular.

Checks if given element is regular.

Parameters:

  • a (defaults to: nil) —

    an element of the monoid

Returns:

  • (Boolean) —

    Result of the check.

Raises:

  • (RLSM::Error) —

    if given element isn’t a monoid element.



846
847
848
849
850
851
852
 
# File 'lib/rlsm/monoid.rb', line 846

def regular?(a=nil)
  if a.nil?
    @elements.all? { |x| regular?(x) }
  else
    @elements.any? { |x| self[a,x,a] == a}
  end
end

#right_ideal(element) ⇒ Array

Calculates the principal right ideal of the given element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Array) —

    Principle right ideal of the given element.

Raises:

  • (RLSM::Error) —

    if the element isn’t a monoid element.



423
424
425
 
# File 'lib/rlsm/monoid.rb', line 423

def right_ideal(element)
  @elements.map { |el| self[element,el] }.uniq.sort(&element_sorter)
end

#right_zero?(element) ⇒ Boolean

Checks if the given element is a right zero element.

Parameters:

  • element —

    An element of the monoid.

Returns:

  • (Boolean) —

    Result of the check.

Raises:

  • (RLSM::Error) —

    if element isn’t a monoid element



521
522
523
524
 
# File 'lib/rlsm/monoid.rb', line 521

def right_zero?(element)
  return false if @order == 1
  @elements.all? { |x| self[x,element] == element }
end

#right_zeros ⇒ Array

Calculates all right zero elements of the monoid.

Returns:

  • (Array) —

    the right zero elements of the monoid.



529
530
531
 
# File 'lib/rlsm/monoid.rb', line 529

def right_zeros
  @elements.select { |el| right_zero?(el) }
end

#set_to_monoid(set) ⇒ Monoid

Transforms a given subset of the elements to a submonoid.

Returns:

  • (Monoid) —

    the submonoid formed by the given set.

Raises:

  • (RLSM::Error) —

    if set isn’t a subset of the monoid elements or the set isn’t a submonoid.



868
869
870
871
872
873
874
 
# File 'lib/rlsm/monoid.rb', line 868

def set_to_monoid(set)
  description = set.map do |el1|
    set.map { |el2| self[el1,el2] }.join(",")
  end

  RLSM::Monoid[ description.join(' ') ]
end

#sorted_subsets ⇒ Array

Calculates a list of all subsets and sorts them.

Returns:

  • (Array) —

    List of subsets sorted by size and lexicographically



903
904
905
906
907
 
# File 'lib/rlsm/monoid.rb', line 903

def sorted_subsets
  subsets = RLSM::ArrayExt::powerset(@elements)

  subsets.sort(&subset_sorter)
end

#submonoids ⇒ Array

Calculates all submonoids.

Returns:

  • (Array) —

    List with all submonoids in it.



365
366
367
368
 
# File 'lib/rlsm/monoid.rb', line 365

def submonoids
  candidates = get_submonoid_candidates
  candidates.map { |set| set_to_monoid(set) }
end

#subset_disjunctive?(set) ⇒ Boolean

Checks if the given set is a disjunctive subset.

Parameters:

  • set (Array) —

    A set of monoid elements

Returns:

  • (Boolean) —

    Result of the check.

Raises:

  • (RLSM::Error) —

    If one of the given elements isn’t a monoid element.



745
746
747
748
749
750
751
752
753
754
755
756
757
758
 
# File 'lib/rlsm/monoid.rb', line 745

def subset_disjunctive?(set)
  tupels = []
  @elements.each do |el1|
    @elements.each do |el2|
	  tupels << [el1, el2]
    end
  end

  tupels.all? do |a,b|
    a == b or tupels.any? do |x,y|
      set.include?(self[x,a,y]) ^ set.include?(self[x,b,y])
    end
  end
end

#subset_sorter ⇒ Proc

Subsets are first ordered by size and then lexicographically.

Returns:

  • (Proc) —

    As argument for the sort method, subsets will be sorted first by size, then lexicographically.



889
890
891
892
893
894
895
896
897
898
 
# File 'lib/rlsm/monoid.rb', line 889

def subset_sorter
  Proc.new do |set1,set2|
    if set1.size == set2.size
      set1.map { |el| @elements.index(el) } <=> 
        set2.map { |el| @elements.index(el) }
    else
      set1.size <=> set2.size
    end
  end
end

#syntactic? ⇒ Boolean

Checks if the monoid is syntactic, i.e. if it has a disjunctive subset.

Returns:

  • (Boolean) —

    Result of the check.



778
779
780
 
# File 'lib/rlsm/monoid.rb', line 778

def syntactic?
  !!disjunctive_subset
end

#to_dfa(finals = nil) ⇒ RLSM::DFA

Transform this monoid into a minimal DFA, which has this monoid as transition monoid.

Parameters:

  • finals (Array) (defaults to: nil) —

    The set of final states in the resulting DFA. Must be a disjunctive subset. If no subset is given, the smallest disjunctive subset is used.

Returns:

  • (RLSM::DFA) —

    A minimal DFA which has this monoid as its transition monoid.

Raises:

  • (RLSM::Error) —

    If given set isn’t a disjunctive subset of the monoid or the monoid isn’t syntactic.



813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
 
# File 'lib/rlsm/monoid.rb', line 813

def to_dfa(finals = nil)
  finals = finals || disjunctive_subset || []

  if syntactic?
    unless all_disjunctive_subsets.include? finals
      raise MonoidError, "#{finals} isn't a disjunctive subset."
    end
  end

  string = "}s#{@elements.index(identity)} "

  finals.each do |element|
    string += "*s#{@elements.index(element)} "
  end

  generating_subset.each do |let|
    @elements.each do |start|
      string += "s#{@elements.index(start)}-#{let}->s#{@elements.index(self[start,let])} "
    end
  end

  RLSM::DFA.new string   
end

#to_regexp(set = nil) ⇒ RLSM::RegExp

Transforms the monoid to a regexp which has this monoid as its syntactic monoid. Each disjunctive subset may yield a different language. If no argument is given, the smallest disjunctive subset is used.

Parameters:

  • set (Array) (defaults to: nil) —

    A disjunctive subset of the monoid.

Returns:

  • (RLSM::RegExp) —

    A regular expression which has this monoi as the syntactic monoid.

Raises:

  • (RLSM::Error) —

    If given set isn’t a disjunctive subset or the monoid isn’t syntactic.



793
794
795
796
797
798
799
 
# File 'lib/rlsm/monoid.rb', line 793

def to_regexp(set = nil)
  unless syntactic?
    raise RLSM::Error, "Only syntactic monoids may be transformed to regexp"
  end
  
  to_dfa(set).to_regexp
end

#to_s ⇒ String

Transforms monoid into a string.

Returns:

  • (String) —

    The string representation of the monoid.



191
192
193
194
195
196
197
198
199
200
201
202
203
204
 
# File 'lib/rlsm/monoid.rb', line 191

def to_s
  result = ""
  sep = @elements.any? { |x| x.to_s.length > 1 } ? ',' : ''
  @table.each_with_index do |el,i|
    result += @elements[el].to_s
    if (i+1) % (@order) == 0
      result += ' '
    else
      result += sep unless i == @order**2 - 1
    end
  end

  result
end

#zero ⇒ nil, Object

Calculates the zero element of the monoid (if it exists).

Returns:

  • (nil) —

    if the monoid has no zero element

  • (Object) —

    the zero element



498
499
500
 
# File 'lib/rlsm/monoid.rb', line 498

def zero
  @elements.find { |el| zero?(el) }
end

#zero? ⇒ Boolean #zero?(element) ⇒ Boolean

Checks if the monoid has a zero element.

Checks if the given element is the zero element.

Parameters:

  • element (defaults to: nil) —

    An element of the monoid.

Returns:

  • (Boolean) —

    Result of the check.

Raises:

  • (RLSM::Error) —

    if element isn’t a monoid element



483
484
485
486
487
488
489
490
491
492
 
# File 'lib/rlsm/monoid.rb', line 483

def zero?(element = nil)
  if element
    return false if @order == 1
    @elements.all? do |el| 
      self[el,element] == element and self[element,el] == element
    end
  else
    !!zero
  end
end