Publication:4003737

zbMath0778.68065MaRDI QIDQ4003737

John M. Howie

Publication date: 23 January 1993

zbMATH Keywords

Turing machines; finite automata; context-free languages; syntactic monoids; rational languages; Kleene's theorem; varieties of languages; right-linear grammars; Pushdown automata; Pumping Lemma

Mathematics Subject Classification ID

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

68Q45: Formal languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Enumerated BSP Automata, ON GROUPS WHICH ARE SYNTACTIC MONOIDS OF DETERMINISTIC CONTEXT-FREE LANGUAGES, Quasi-injectivity of partially ordered acts, Anisimov's Theorem for inverse semigroups, Restricted Burnside problem for semigroups and its application to language theory, Quasi injectivity andθ-internal order sum in partially ordered acts, Undecidability of the word problem for Yamamura's HNN-extension under nice conditions., Ideal regular languages and strongly connected synchronizing automata, Representations of commutative asynchronous automata, John Macintosh Howie: work and legacy, Languages with membership determined by single letter factors, The applications of solid codes to r-R and r-D languages, Cayley graphs as classifiers for data mining: the influence of asymmetries, A Munn type representation for a class of \(E\)-semiadequate semigroups, A method for the construction of complete congruences on lattices of pseudovarieties, An equivalence relation on \(\{ 0,1\}^*\), Some results in \(r\)-disjunctive languages and related topics, Completely simple codes, On the homological classification of semigroups with local units, Extremal synchronizing circular automata, A geometric approach to (semi)-groups defined by automata via dual transducers., A sufficient condition to polynomially compute a minimum separating DFA, Freeness of automaton groups vs boundary dynamics, Groups and semigroups defined by colorings of synchronizing automata, On finite generation and presentability of Schützenberger products, Unnamed Item