Concatenation of inputs in a two-way automaton
type: Item
instance of: scholarly article
title: Concatenation of inputs in a two-way automaton
zbMATH Open document ID: 0664.68081
DOI: 10.1016/0304-3975(89)90075-3
author: J.-C. Birget
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: To every input string of a two-way automaton one associates a quadruple of partial functions (or relations) between the states. This quadruple describes the behavior of the automaton on that input, and can also be used to formulate acceptance, or notions like the crossing sequence. Formulas are given that show how two such quadruples are combined (``multiplied'') as their corresponding input strings are concatenated.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 4087054
zbMATH Keywords: concatenation of inputs
zbMATH Keywords: two-way transformation semigroups
zbMATH Keywords: subset construction
zbMATH Keywords: crossing sequence
zbMATH Keywords: global transition maps
zbMATH Keywords: Birget semigroup
zbMATH Keywords: two-way automaton
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90075-3
OpenAlex ID: W1985201105
cites work: Q3859267
cites work: Two-way automaton computations
cites work: Q4079524
cites work: Q5592246
cites work: Q3853827
cites work: Q3741089
cites work: Q5526130
cites work: Q5541339
cites work: Q5541340
description: scientific article; zbMATH DE number 4087054