Paper Info
Title
Equations between regular terms and an application to process logic
Abstract
Regular terms with the Kleene operations &ugr;,;, and * can be thought of as operators on languages, generating other languages. An equation r1 &equil; r2 between two such terms is said to be satisfiable just in case languages exist which make this equation true. We show that the satisfiability problem even for *-free regular terms is undecidable. Similar techniques are used to show that a very natural extension of the Process Logic of Harel, Kozen and Parikh is undecidable.
Year
DOI
Venue
1981
10.1145/800076.802493
STOC
Keywords
Field
DocType
satisfiability problem,similar technique,regular term,case language,process logic,natural extension,kleene operation,equation r1,free regular term,petri net,decidability,satisfiability
Discrete mathematics,Combinatorics,Petri net,Computer science,Vector addition system,Boolean satisfiability problem,Decidability,Operator (computer programming),Reachability problem,Process logic,Undecidable problem
Conference
Citations 
PageRank 
References 
15
4.72
4
Authors
4
Name
Order
Citations
PageRank
Ashok K. Chandra131161215.02
Joseph Y. Halpern296171618.10
Albert R. Meyer31729604.47
Rohit Parikh41510540.65