Paper Info
Title
Propositional Automata and Cell Automata: Representational Frameworks for Discrete Dynamic Systems
Abstract
This paper describes and compares two simple, powerful models for formalizing the behavior of discrete dynamic systems: Propositional and Cell Automata. Propositional Automata encode state in terms of boolean propositions, and behavior in terms of boolean gates and latches. Cell Automata generalize the propositional model by encoding state in terms of multi-valued cells, and behavior in terms of comparators and selectors that respond to cell values. While the models are equally expressive, Cell Automata are computationally more efficient than Propositional Automata. Additionally, arbitrary Propositional Automata can be converted to optimal Cell Automata with identical behavioral properties, and Cell Automata can be encoded as a Propositional Automata with only logarithmic increase in size.
Year
DOI
Venue
2008
10.1007/978-3-540-89378-3_6
Australasian Conference on Artificial Intelligence
Keywords
Field
DocType
boolean gate,cell automata,propositional automata encode state,cell value,boolean proposition,arbitrary propositional automata,discrete dynamic system,propositional automata,representational frameworks,propositional model,discrete dynamic systems,encoding state
Discrete mathematics,Quantum finite automata,Automata theory,Continuous spatial automaton,Nested word,Mobile automaton,Automaton,Theoretical computer science,Propositional variable,Mathematics,ω-automaton
Conference
Volume
ISSN
Citations 
5360
0302-9743
6
PageRank 
References 
Authors
0.86
7
3
Name
Order
Citations
PageRank
Eric Schkufza125913.58
Nathaniel Love223919.59
Michael R. Genesereth32447830.52