Automatiserat resonemang om system med oändliga domäner kräver en utvidgning av automata, och i synnerhet, regelbunden automata, till oändliga alfabet. Befintliga formalismer av sådan automata klara av oändligheten av alfabetet genom att lägga till automaton en uppsättning register eller småstenar, eller genom att tillskriva alfabetet genom etiketter från en extra finit alfabet som läses av en mellanliggande transducer. Dessa formalismer innefattar en komplicerad mekanism utöver automaternas övergångsfunktion över finita alfabet och är därför svåra att förstå och arbeta med. Vi introducerar och studerar variabel finit automata över oändliga alfabet (VFA). VFA bildar en naturlig och enkel förlängning av regelbunden (och -regelbunden) automata, där alfabetet består av bokstäver samt variabler som sträcker sig över det oändliga alfabetet domän. Därför har VFA samma struktur som vanlig automata, bara att några av övergångarna är märkta med variabler. Vi jämför VFA med befintliga formalismer och studerar deras stängningsegenskaper och klassiska beslutsproblem. Vi tänker på både finita och oändliga ord. Dessutom identifierar och studerar vi det deterministiska fragmentet av VFA. Vi visar att även om detta fragment är tillräckligt starkt för att uttrycka många intressanta egenskaper, är det stängt under union, skärningspunkt och komplettering, och dess icke-tomhet och inneslutningsproblem är avgörande. Slutligen beskriver vi en determiniseringsprocess för en determinizable subgrupp av VFA.
I REF introducerade vi VNFAs - icke-deterministiska finita automata förstärkt av variabler.
Variable Automata over Infinite Alphabets
{'venue': 'LATA', 'journal': None, 'mag_field_of_study': ['Computer Science']}