The Library
Graph representation functions computable by finite automata
Tools
Lozin, Vadim V. (2008) Graph representation functions computable by finite automata. Journal of Automata, Languages and Combinatorics, Vol.13 (No.1). pp. 73-90. ISSN 1430-189X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://www.jalc.de
Abstract
We consider a simple model for representing a graph in computer memory in which every vertex is assigned a word in a finite alphabet - vertex code - and the adjacency of two vertices is a function Ψ of their codes. The function Ψ is called the representation function. We say that Ψ is universal if a Ψ-representation exists for every simple graph G. In this paper, we study representation functions computable by automata with two states. The main result is a criterion characterizing the universal functions. In the case of binary alphabet, we provide some bounds on the dimension of minimum Ψ-representation.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Journal of Automata, Languages and Combinatorics | ||||
Publisher: | Otto-von-Guericke-Universitaet Magdeburg, Fakultaet fuer Informatik | ||||
ISSN: | 1430-189X | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.13 | ||||
Number: | No.1 | ||||
Page Range: | pp. 73-90 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |