Skip to content

An algorithm that decide if a finite deterministic automaton accepts a set definable in FO[<,mod]

Notifications You must be signed in to change notification settings

Arthur-Milchior/RegAut

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

This program has been written by Arthur Milchior as part of his Computer Science PhD at University Paris Diderot.

It can be compiled with 
ocamlbuild main.native

The program can run in two modes
In the mode input (default), the program reads a file (by default the file is  ./input, it can otherwise be changed with the command line argument «-input Input_File»), containing automata. The   EBNF of this file is given in automaton.ebnf
the program print "Name of the automaton:OK: a formula defining the set accepted by the state" if the automaton accepts a state definable in the logic, or
"name of the automaton: its description: the property it does not satisfy" otherwise

Note that only the program currently considers only automata reading
set of non-negative integers. The options -none, -quantifier-free and -existential selects whether our algorithm generate no formula, quantifier-free formulas(takes exponential-time), or existential formulas(takes polynomial-time).

In the mode random, selected by the option -random, 1 (or the argument given after the option -number) formulas F of length 10 (or the argument given after the option -size) in dimension 2 (or the argument given after the option -dimension) and base 4 (or the argument given after the option -base). The minimal automaton A accepting the set defined by F is then computed using Büchi-Bruyère algorithm. Our algorithm is then applied to A. The computation time of our algorithm is then appended to formula.dat (this file must already exists)

Arthur@milchior.fr

About

An algorithm that decide if a finite deterministic automaton accepts a set definable in FO[<,mod]

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages