Please enable JavaScript.
Coggle requires JavaScript to display documents.
Groupings of Papers with NSDB - Coggle Diagram
Groupings of Papers with NSDB
Automata-Specialized
Needs:
need to define automata theory and classify languages based on simple logical tools, or through an algorithmic approach
need to define complexity hierarchies of languages
Solutions:
a logical / algorithmic approach that can intuitively provide the basics of automata theory
Papers:
J. Sakarovitch, Elements of automata theory
JE-Hopcroft, R Motwani, JD-Ulman, Introduction to automata theory, langauges and computation
Differences:
unlike the algebraic approach, this approach uses algorithmic descriptions of computational models
Benefits:
more accessible / more intuitive than algebraic approach
allows one to define complexity hierarchies without need for much formalism
Algebraic Approach to Automata Theory
Needs:
need to use more precise tools to define classes of languages
need to define sufficient and necessary conditions to describe certain languages that are hard to describe intuitively, i.e. star-free languages
need to view automata theory from an alternative perspective
Solutions:
use of finite semigroups and finite monoids
characterization of regular languages using structure of finite monoids, i.e. star-free languages have aperiodic finite monoids
Differences:
use of finite monoid structure instead of graphical / logical approach
less accessible than logical / algorithmic approach, and relies on more formal methods
Benefits:
necessary and sufficient conditions for certain languages are described, which may not be possible in other approaches
intersects with other areas of math / opens the door for other mathematical tools to be applied
Papers:
S. Eilenberg, Automata, languages, and machines
J-E Pin, Syntactic Semigroups
MP Schutzenberger, On finite monoids having only trivial subgroups
J-E Pin, Mathematical foundations of automata theory
Topological Approach
Needs:
need for tools that can classify languages with more accuracy
need to classify languages with words of arbitrary length
Solutions:
use of topology to describe how sets / languages behave as words arbitrarily long lengths
construction of a metric that can 'measure' the distance between words / languages
Papers:
J-E Pin, Topologies for the free monoid
J-E Pin, Profinite methods for automata theory
Benefits:
the profinite approach provides clearer / more concise proofs to define languages as it considers how words behave as their lengths approach infinity
opens the door towards defining varieties of languages within the regular (or rational) class of languages
Differences:
topological approach also uses profinite words aside from ordinary words
profinite words generalize the notion of idempotent
Algebraic Support
Needs:
need to define the algebraic structure / relationship of algebraic objects such as semigroups / monoids
Solutions:
structure of semigroups are comprehensively defined using Green's relations, namely, H, R, L, J, and D relations
Clifford and Preston's location theorem provides sufficient and necessary conditions to define whether a D-class of a semigroup contains an idempotent
Papers:
JA-Green, On the structure of semigroups
AH-Clifford and GB Preston, The algebraic theory of semigroups
Differences:
other methods do not provide as clear a description of a semigroup as Green's relations
Benefits:
Green's relations are more comprehensive than other methods