@inproceedings{10.1007/978-3-642-29952-0_37,
    Abstract = {We introduce a finite automata model for performing computations over an arbitrary structure {\$}{\backslash}mathcal S{\$}. The automaton processes sequences of elements in {\$}{\backslash}mathcal S{\$}. While processing the sequence, the automaton tests atomic relations, performs atomic operations of the structure {\$}{\backslash}mathcal S{\$}, and makes state transitions. In this setting, we study several problems such as closure properties, validation problem and emptiness problems. We investigate the dependence of deciding these problems on the underlying structures and the number of registers of our model of automata. Our investigation demonstrates that some of these properties are related to the existential first order fragments of the underlying structures.},
    Address = {Berlin, Heidelberg},
    Author = {Gandhi, Aniruddh and Khoussainov, Bakhadyr and Liu, Jiamou},
    BookTitle = {Theory and Applications of Models of Computation},
    Editor = {Agrawal, Manindra and Cooper, S. Barry and Li, Angsheng},
    File = {Finite Automata over Structures - Gandhi2012\_Chapter\_FiniteAutomataOverStructures - a - m.pdf},
    ISBN = {978-3-642-29952-0},
    Pages = {373--384},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Finite Automata over Structures},
    Year = {2012},
    date-added = {2020-10-30 14:10:54 +0100},
    date-modified = {2020-10-30 14:10:54 +0100},
    doi = {10.1007/978-3-642-29952-0_37}
}

@inproceedings{10.1007/978-3-642-29952-0_37, Abstract = {We introduce a finite automata model for performing computations over an arbitrary structure {\$}{\backslash}mathcal S{\$}. The automaton processes sequences of elements in {\$}{\backslash}mathcal S{\$}. While processing the sequence, the automaton tests atomic relations, performs atomic operations of the structure {\$}{\backslash}mathcal S{\$}, and makes state transitions. In this setting, we study several problems such as closure properties, validation problem and emptiness problems. We investigate the dependence of deciding these problems on the underlying structures and the number of registers of our model of automata. Our investigation demonstrates that some of these properties are related to the existential first order fragments of the underlying structures.}, Address = {Berlin, Heidelberg}, Author = {Gandhi, Aniruddh and Khoussainov, Bakhadyr and Liu, Jiamou}, BookTitle = {Theory and Applications of Models of Computation}, Editor = {Agrawal, Manindra and Cooper, S. Barry and Li, Angsheng}, File = {Finite Automata over Structures - Gandhi2012_Chapter_FiniteAutomataOverStructures - a - m.pdf}, ISBN = {978-3-642-29952-0}, Pages = {373--384}, Publisher = {Springer Berlin Heidelberg}, Title = {Finite Automata over Structures}, Year = {2012}, date-added = {2020-10-30 14:10:54 +0100}, date-modified = {2020-10-30 14:10:54 +0100}, doi = {10.1007/978-3-642-29952-0_37} }