Reference. Definable operations in general algebras, and the theory of automata and flowcharts

Hans Bekić · Programming languages and their definition: H. Bekič (1936–1982) · 1984 · parsing · DOI
We study the class of operations definable from the given operations of an algebra of sets by union, composition, and fixed points; we obtain two theorems on definable operations that give us as special case the regular-equals-recognisable theorem of generalised finite automata theory. Definable operations arise also as the operations computable by charts; by translating into predicate logic, we obtain Manna’s formulas for termination and correctness of flowcharts.

Cite
Cite as @Bekić1984 (helia, typst) · \cite{Bekić1984} (LaTeX)
BibTeX
bibtex · 14 lines
@incollection{Bekić1984,
 title = {Definable operations in general algebras, and the theory of automata and flowcharts},
 author = {Bekić, Hans},
 year = {1984},
 isbn = {978-3-540-38933-0},
 doi = {10.1007/BFb0048939},
 url = {https://doi.org/10.1007/BFb0048939},
 booktitle = {Programming languages and their definition: {H}. {Bekič} (1936–1982)},
 editor = {Jones, C. B.},
 pages = {30--55},
 publisher = {Springer Berlin Heidelberg},
 address = {Berlin, Heidelberg},
 abstract = {We study the class of operations definable from the given operations of an algebra of sets by union, composition, and fixed points; we obtain two theorems on definable operations that give us as special case the regular-equals-recognisable theorem of generalised finite automata theory. Definable operations arise also as the operations computable by charts; by translating into predicate logic, we obtain Manna's formulas for termination and correctness of flowcharts.}
}
hayagriva YAML (typst)
yaml · 18 lines
Bekić1984:
  type: anthos
  title: Definable operations in general algebras, and the theory of automata and flowcharts
  author: Bekić, Hans
  date: 1984
  editor: Jones, C. B.
  page-range: 30-55
  url: https://doi.org/10.1007/BFb0048939
  serial-number:
    doi: 10.1007/BFb0048939
    isbn: 978-3-540-38933-0
  abstract: We study the class of operations definable from the given operations of an algebra of sets by union, composition, and fixed points; we obtain two theorems on definable operations that give us as special case the regular-equals-recognisable theorem of generalised finite automata theory. Definable operations arise also as the operations computable by charts; by translating into predicate logic, we obtain Manna's formulas for termination and correctness of flowcharts.
  parent:
    type: anthology
    title: 'Programming languages and their definition: {H}. {Bekič} (1936–1982)'
    publisher:
      name: Springer Berlin Heidelberg
      location: Berlin, Heidelberg
Download: Bekić1984.bib · Bekić1984.yml
Cited by (2)

Cartesian Cubical Computational Type Theory: Constructive Reasoning with Paths and Equalities angiuli-2018-cartesianCSL · 2018
We present a dependent type theory organized around a Cartesian notion of cubes (with faces, degeneracies, and diagonals), supporting both fibrant and non-fibrant types. The fibrant fragment validates Voevodsky’s univalence axiom and includes a circle type, while the non-fibrant fragment includes exact (strict) equality types satisfying equality reflection. Our type theory is defined by a semantics in cubical partial equivalence relations, and is the first two-level type theory to satisfy the canonicity property: all closed terms of boolean type evaluate to either true or false.
DOI · arXiv

Infinitary Axiomatization of the Equational Theory of Context-Free Languages grathwohl_infinitary_2013EPTCS · 2013
We give a natural complete infinitary axiomatization of the equational theory of the context-free languages, answering a question of Lei\\textbackslashss\ (1992).
DOI
Cites 15 works (0 here)
External (15)
Bekić1984 reference entries/refs/Bekić1984/Bekić1984.hel