Integer Weighted Automata on Infinite Words
| Autor: | Igor Potapov, Reino Niskanen, Vesa Halava, Tero Harju |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Finite-state machine Reduction (recursion theory) Universality (philosophy) Nonlinear Sciences::Cellular Automata and Lattice Gases Undecidable problem Automaton Post correspondence problem TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computer Science (miscellaneous) Word problem (mathematics) Computer Science::Formal Languages and Automata Theory Mathematics Integer (computer science) |
| Zdroj: | Developments in Language Theory ISBN: 9783030815073 DLT |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054122440014 |
| Popis: | In this paper we combine two classical generalisations of finite automata (weighted automata and automata on infinite words) into a model of integer weighted automata on infinite words and study the universality and the emptiness problems under zero weight acceptance. We show that the universality problem is undecidable for three-state automata by a direct reduction from the infinite Post correspondence problem. We also consider other more general acceptance conditions as well as their complements with respect to the universality and the emptiness problems. Additionally, we build a universal integer weighted automaton with fixed transitions. This automaton has an additional integer input that allows it to simulate any semi-Thue system. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|