Uniform and nonuniform recognizability
| Autor: | Wolfgang Thomas |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES General Computer Science Algebraic structure Structure (category theory) Picture languages Monadic predicate calculus Signature (logic) Theoretical Computer Science Nondeterministic algorithm Algebra Graph language TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Homomorphism Monadic second-order logic Tree automaton Recognizability Algebraic number Tree language Computer Science::Formal Languages and Automata Theory Computer Science(all) Mathematics |
| Zdroj: | Theoretical Computer Science. (1):299-316 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/S0304-3975(01)00229-8 |
| Popis: | Deterministic and nondeterministic finite-state recognizability over finite structures are introduced in an algebraic setting, avoiding detailed computational conventions as needed in the definition of finite-state acceptors. For deterministic recognizability, the classical approach is adopted, using a “uniform” homomorphism from the input domain (consisting of terms) into a finite algebra. For the nondeterministic case, we refer to relational input structures and to an acceptance via relational homomorphisms (which are applied “nonuniformly” since they depend on the input structures). We show how this approach encompasses known models of nondeterministic automata over finite words, trees, pictures, and graphs, and present some elementary metaresults connecting uniform recognizability, nonuniform recognizability, and monadic second-order logic. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|