Second-Order Finite Automata: Expressive Power and Simple Proofs Using Automatic Structures

Autor:	Dietrich Kuske
Rok vydání:	2021
Předmět:	Algebra Finite-state machine Closure (mathematics) Computer science Simple (abstract algebra) Semantics (computer science) Order (group theory) Mathematical proof Decidability Automaton
Zdroj:	Developments in Language Theory ISBN: 9783030815073 DLT
Popis:	Second-order finite automata, introduced recently by Andrade de Melo and de Oliveira Oliveira, represent classes of languages. Since their semantics is defined by a synchronized rational relation, they can be studied using the theory of automatic structures. We exploit this connection to uniformly reprove and strengthen known and new results regarding closure and decidability properties concerning these automata. We then proceed to characterize their expressive power in terms of automatic classes of languages studied by Jain, Luo, and Stephan.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::d885779bd8ccc5ec325109605d39d87a https://doi.org/10.1007/978-3-030-81508-0_20 Zobrazit plný text záznamu