Paper Info
Title
Thue specifications and their monadic second-order properties
Abstract
This paper introduces oriented Thue specifications and their models which are simple directed edge-labeled graphs. The monadic second-order theory of these models is investigated and shown decidable for the class of suffix-bounded rational oriented Thue specifications. In addition, a characterization of prefix-closed context-free languages is given in terms of oriented Thue specifications.
Year
DOI
Venue
1999
10.3233/FI-1999-39305
Fundam. Inform.
Keywords
Field
DocType
suffix-bounded rational oriented thue,thue specification,monadic second-order theory,monadic second-order properties,thue specifications,monadic second-order property,prefix-closed context-free language,edge-labeled graph,oriented thue specification,automata
Discrete mathematics,Graph,Combinatorics,Automaton,Monadic second-order logic,Decidability,Mathematics,Monadic predicate calculus,Monad (functional programming)
Journal
Volume
Issue
Citations 
39
3
7
PageRank 
References 
Authors
0.54
12
2
Name
Order
Citations
PageRank
Teodor Knapik122216.13
Hugues Calbrix2342.63