Two-Head Finite-State Acceptors with Translucent Letters
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer International Publishing Ag
Access Rights
info:eu-repo/semantics/closedAccess
Abstract
Finite-state acceptors are studied that have two heads that read the input from opposite sides. In addition, a set of translucent letters is associated with each state. It is shown that these two-head automata are strictly more expressive than the model with a single head, but that they still only accept languages that have a semi-linear Parikh image. In fact, we obtain a characterization for the class of linear context-free trace languages in terms of a specific class of two-head finite-state acceptors with translucent letters.
Description
45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) -- JAN 27-30, 2019 -- Novy Smokovec, SLOVAKIA
Keywords
Two-head finite-state acceptor, Translucent letter, Linear context-free language, Semi-linear Parikh set, Trace language
Journal or Series
Theory and Practice of Computer Science, Sofsem 2019
WoS Q Value
Scopus Q Value
Volume
11376
