Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Quantitative Semantics on Jumping Finite Automata
event speaker icon
Ishai Salgado (M.Sc. Thesis Seminar)
event date icon
Sunday, 16.06.2024, 14:30
event location icon
Zoom Lecture: 94576770275 & Taub 301
event speaker icon
Advisor: Dr. Shaull Almagor
Jumping automata are finite automata that read their input in a non-sequential manner, by allowing a reading head to “jump” between positions on the input, consuming a permutation of the input word. We argue that allowing the head to jump should incur some cost. To this end, we propose three quantitative semantics for jumping automata, whereby the jumps of the head in an accepting run define the cost of the run. The three semantics correspond to different interpretations of jumps: the absolute distance semantics counts the distance the head jumps, the reversal semantics counts the number of times the head changes direction, and the Hamming distance measures the number of letter-swaps the run makes. We study these measures, with the main focus being the boundedness problem: given a jumping automaton, decide whether its (quantitative) languages are bounded by some given number k. We establish the decidability and complexity for this problem under several variants.