请输入您要查询的字词:

 

单词 AutomaticPresentation
释义

automatic presentation


Let S be a relational structure (for example, a graph).

S has an automatic presentation if (for some alphabet Σ) there is a languagePlanetmathPlanetmath LΣ* and a surjective map f from L onto the ) of S such that

  • L can be checked by a finite automaton (http://planetmath.org/DeterministicFiniteAutomaton) (Membership)

  • The language of all convolutions of x,yL where f(x)=f(y) can be checked by a (Equality)

  • For all n-ary relationsMathworldPlanetmathPlanetmathPlanetmath (http://planetmath.org/Relation) Ri in S, the language of all convolutions of x1,x2,,xnL where Ri(f(x1),f(x2),,f(xn)) can be checked by a ()

The class of languages accepted by finite automata, i.e. regular languages, is closed underPlanetmathPlanetmath operations like union, intersectionMathworldPlanetmathPlanetmath, complementation etc, and it is decidable whether or not a finite accepts the empty language. This allows any first order sentenceMathworldPlanetmath over the structureMathworldPlanetmath to be decided - using union for ’and’, complementation for ’not’ etc., and emptiness for dealing with ’there exists’. As such, the first order theory of any structure with an automatic presentation is decidable.

Note that wrt group this is inspired by, but not to, the definition of automatic groupsMathworldPlanetmath.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 21:07:07