stamps.py

from compAut.algebra import FiniteMonoid, FiniteSemigroup
from compAut.algebra.semigroups import cache_memb
import itertools

class Stamp:
	"""
	A morphism from free monoids to a finite monoid.
	Essentially a FiniteMonoid with explicit generators.
	__call__ work to maps the free monoid to the finite monoids
	.product  is there to access to the underlying product.
	.cayley_succ take a monoid element, a letter and compute its successor.
	Its using the underlying Cayley graph of the monoid.


	The terminology stem from classical semigroup theory [1].
	The notion is more general than the classical syntactic monoid/semigroup and
	is important to decides some properties than requires the generators to be included into
	the algeba.

	H.  Straubing,
	On logical descriptions of regular languages, in LATIN 2002, Berlin, 2002, pp. 528–538,Lect. Notes Comp. Sci.n ̊2286, Springer.
	"""

	def __init__(self, Monoid, mapping, empty_word):
		"""
		Mapping is a dict-like, monoid a FiniteMonoid.
		Alphabet are the key of the mapping. Values should
		be within the monoid.
		"""
		self.mapping = mapping
		self._empty_word = empty_word
		self._monoid = Monoid
		self._cache_memb = {}

	def map_letter(self, letter):
		for l,v  in self.mapping.items():
			try:
				if letter in l:
					return v
			except:
				pass
		return None
	def __call__(self, *words):
		return self.monoid(*map(self.map_letter, itertools.chain(*words)))

	@property
	def monoid(self):
		return self._monoid

	@cache_memb
	def stable_semigroup(self):
		A = [v for k,v in self.mapping.items() if k != self._empty_word]
		S = set(A)
		monoid = self.monoid
		k = 1
		while not monoid.is_subsemigroup(S):
			S = set(monoid(x, y) for x in S for y in A)
			k += 1
		S = FiniteSemigroup(S, product=self.monoid)
		S.stability_index = k
		return S

	def k_stable_semigroup(self, k):
		"""
			Return the subsemigroup generated by words of length k.
		"""
		A = set([v for k,v in self.mapping.items() if k != self._empty_word])
		S = set(A)
		monoid = self.monoid
		for _ in range(k):
			S = set(monoid(x, y) for x in S for y in A)
		return FiniteSemigroup.generated_by(S, product=monoid)
			

	def is_QA(self):
		return self.stable_semigroup().is_aperiodic()

	def is_QDA(self):
		return self.stable_semigroup().is_DA()

	def is_QLDA(self):
		return self.stable_semigroup().is_LDA()

	def is_QSG(self):
		return self.stable_semigroup().is_SG()

	def is_QZG(self):
		return self.stable_semigroup().is_ZG()

	def is_QLZG(self):
		return self.stable_semigroup().is_LZG()

	def left_cayley_semi_automaton(self):
		from compAut.models.finiteautomata import SemiAutomaton
		mapping = self.mapping.copy()
		return SemiAutomaton.from_transitions((m, l, self.monoid(n, m)) for m in self.monoid for l, n in mapping.items())

	def right_cayley_semi_automaton(self):
		from compAut.models.finiteautomata import SemiAutomaton
		mapping = self.mapping.copy()
		return SemiAutomaton.from_transitions((m, l, self.monoid(m, n)) for m in self.monoid for l, n in mapping.items())