java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig20.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:18:01,556 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:18:01,581 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:18:01,596 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:18:01,596 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:18:01,597 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:18:01,601 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:18:01,604 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:18:01,607 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:18:01,608 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:18:01,609 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:18:01,609 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:18:01,610 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:18:01,614 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:18:01,615 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:18:01,616 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:18:01,629 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:18:01,631 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:18:01,632 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:18:01,633 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:18:01,634 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:18:01,640 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:18:01,641 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:18:01,641 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:18:01,642 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:18:01,643 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:18:01,643 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:18:01,646 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:18:01,647 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:18:01,647 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:18:01,648 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:18:01,648 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:18:01,648 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:18:01,656 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:18:01,657 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:18:01,657 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:18:01,678 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:18:01,679 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:18:01,679 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:18:01,679 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:18:01,681 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:18:01,681 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:18:01,682 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:18:01,682 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:18:01,682 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:18:01,682 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:18:01,682 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:18:01,682 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:18:01,683 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:18:01,683 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:18:01,683 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:18:01,683 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:18:01,683 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:18:01,685 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:18:01,686 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:18:01,731 INFO ]: Repository-Root is: /tmp [2018-06-22 05:18:01,770 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:18:01,774 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:18:01,776 INFO ]: Initializing SmtParser... [2018-06-22 05:18:01,776 INFO ]: SmtParser initialized [2018-06-22 05:18:01,783 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig20.c.smt2 [2018-06-22 05:18:01,784 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 05:18:02,214 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig20.c.smt2 unknown [2018-06-22 05:18:02,765 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig20.c.smt2 [2018-06-22 05:18:02,788 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:18:02,795 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:18:02,796 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:18:02,796 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:18:02,796 INFO ]: ChcToBoogie initialized [2018-06-22 05:18:02,800 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:18:02" (1/1) ... [2018-06-22 05:18:02,929 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02 Unit [2018-06-22 05:18:02,929 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:18:02,931 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:18:02,931 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:18:02,931 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:18:02,953 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (1/1) ... [2018-06-22 05:18:02,953 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (1/1) ... [2018-06-22 05:18:02,961 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (1/1) ... [2018-06-22 05:18:02,961 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (1/1) ... [2018-06-22 05:18:02,969 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (1/1) ... [2018-06-22 05:18:02,971 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (1/1) ... [2018-06-22 05:18:02,973 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (1/1) ... [2018-06-22 05:18:02,975 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:18:02,976 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:18:02,976 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:18:02,976 INFO ]: RCFGBuilder initialized [2018-06-22 05:18:02,977 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 05:18:03,018 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:18:03,019 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:18:03,019 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:18:03,019 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:18:03,019 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:18:03,019 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:18:03,346 INFO ]: Using library mode [2018-06-22 05:18:03,347 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:18:03 BoogieIcfgContainer [2018-06-22 05:18:03,347 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:18:03,350 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:18:03,350 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:18:03,353 INFO ]: TraceAbstraction initialized [2018-06-22 05:18:03,353 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:18:02" (1/3) ... [2018-06-22 05:18:03,354 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@40704cdd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:18:03, skipping insertion in model container [2018-06-22 05:18:03,355 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:18:02" (2/3) ... [2018-06-22 05:18:03,355 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@40704cdd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:18:03, skipping insertion in model container [2018-06-22 05:18:03,355 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:18:03" (3/3) ... [2018-06-22 05:18:03,357 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:18:03,365 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:18:03,372 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:18:03,409 INFO ]: Using default assertion order modulation [2018-06-22 05:18:03,410 INFO ]: Interprodecural is true [2018-06-22 05:18:03,410 INFO ]: Hoare is false [2018-06-22 05:18:03,410 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:18:03,410 INFO ]: Backedges is TWOTRACK [2018-06-22 05:18:03,410 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:18:03,410 INFO ]: Difference is false [2018-06-22 05:18:03,410 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:18:03,410 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:18:03,424 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:18:03,490 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:18:03,490 INFO ]: Found error trace [2018-06-22 05:18:03,491 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:18:03,491 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:18:03,513 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-22 05:18:03,515 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:18:03,515 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:18:03,572 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:03,572 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:18:03,572 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:03,667 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:03,790 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:18:03,792 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:18:03,792 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:18:03,796 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:18:03,822 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:18:03,822 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:18:03,852 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:18:04,012 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:18:04,013 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:18:04,013 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:18:04,014 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:18:04,015 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:18:04,051 INFO ]: With dead ends: 9 [2018-06-22 05:18:04,051 INFO ]: Without dead ends: 9 [2018-06-22 05:18:04,052 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:18:04,095 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:18:04,117 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:18:04,119 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:18:04,119 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:18:04,120 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:18:04,120 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:18:04,120 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:18:04,120 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:18:04,120 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:18:04,121 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:18:04,121 INFO ]: Found error trace [2018-06-22 05:18:04,121 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:18:04,121 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:18:04,121 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-22 05:18:04,121 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:18:04,121 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:18:04,122 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:04,122 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:18:04,122 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:04,199 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:04,393 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:18:04,393 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:18:04,393 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:18:04,401 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:18:04,461 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:04,473 INFO ]: Computing forward predicates... [2018-06-22 05:18:04,790 WARN ]: Spent 167.00 ms on a formula simplification. DAG size of input: 6 DAG size of output: 1 [2018-06-22 05:18:05,048 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:18:05,070 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:18:05,070 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 05:18:05,071 INFO ]: Interpolant automaton has 5 states [2018-06-22 05:18:05,071 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 05:18:05,071 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:18:05,071 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 05:18:05,230 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:18:05,230 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 05:18:05,230 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 05:18:05,231 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 05:18:05,231 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:18:05,231 INFO ]: With dead ends: 10 [2018-06-22 05:18:05,231 INFO ]: Without dead ends: 10 [2018-06-22 05:18:05,232 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:18:05,232 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 05:18:05,233 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 05:18:05,233 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 05:18:05,234 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 05:18:05,235 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 05:18:05,235 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:18:05,235 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 05:18:05,235 INFO ]: Interpolant automaton has 5 states. [2018-06-22 05:18:05,235 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 05:18:05,235 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 05:18:05,235 INFO ]: Found error trace [2018-06-22 05:18:05,235 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:18:05,236 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:18:05,236 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-22 05:18:05,236 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:18:05,236 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:18:05,237 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:05,237 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:18:05,237 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:05,360 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:05,653 WARN ]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 05:18:05,758 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:18:05,758 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:18:05,758 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:18:05,764 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:18:05,842 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:18:05,842 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:05,846 INFO ]: Computing forward predicates... [2018-06-22 05:18:06,082 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 8 [2018-06-22 05:18:07,465 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:18:07,485 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:18:07,485 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-22 05:18:07,485 INFO ]: Interpolant automaton has 6 states [2018-06-22 05:18:07,486 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 05:18:07,486 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:18:07,486 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-22 05:18:07,541 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:18:07,541 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 05:18:07,543 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 05:18:07,543 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-22 05:18:07,543 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:18:07,543 INFO ]: With dead ends: 12 [2018-06-22 05:18:07,543 INFO ]: Without dead ends: 12 [2018-06-22 05:18:07,544 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2018-06-22 05:18:07,544 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 05:18:07,545 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 05:18:07,545 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 05:18:07,546 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 05:18:07,546 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 9 [2018-06-22 05:18:07,546 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:18:07,546 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 05:18:07,546 INFO ]: Interpolant automaton has 6 states. [2018-06-22 05:18:07,546 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 05:18:07,546 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 05:18:07,546 INFO ]: Found error trace [2018-06-22 05:18:07,546 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:18:07,547 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:18:07,547 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-22 05:18:07,547 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:18:07,547 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:18:07,548 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:07,548 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:18:07,548 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:07,618 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:07,832 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 4 DAG size of output: 1 [2018-06-22 05:18:08,076 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:18:08,076 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:18:08,076 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:18:08,083 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:18:08,186 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 05:18:08,186 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:08,191 INFO ]: Computing forward predicates... [2018-06-22 05:18:15,158 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:18:15,180 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:18:15,180 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-22 05:18:15,181 INFO ]: Interpolant automaton has 8 states [2018-06-22 05:18:15,181 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 05:18:15,181 INFO ]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:18:15,181 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 8 states. [2018-06-22 05:18:15,387 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 7 [2018-06-22 05:18:15,554 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:18:15,554 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 05:18:15,554 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 05:18:15,554 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-22 05:18:15,554 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:18:15,555 INFO ]: With dead ends: 13 [2018-06-22 05:18:15,555 INFO ]: Without dead ends: 13 [2018-06-22 05:18:15,555 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=55, Invalid=77, Unknown=0, NotChecked=0, Total=132 [2018-06-22 05:18:15,555 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 05:18:15,556 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 05:18:15,556 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 05:18:15,557 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 05:18:15,557 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-22 05:18:15,557 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:18:15,557 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 05:18:15,557 INFO ]: Interpolant automaton has 8 states. [2018-06-22 05:18:15,557 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 05:18:15,557 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 05:18:15,557 INFO ]: Found error trace [2018-06-22 05:18:15,558 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:18:15,558 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:18:15,558 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 4 times [2018-06-22 05:18:15,558 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:18:15,558 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:18:15,558 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:15,558 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:18:15,558 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:18:15,626 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:16,029 WARN ]: Spent 177.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 11 [2018-06-22 05:18:16,104 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:18:16,104 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:18:16,104 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:18:16,110 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 05:18:16,188 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 05:18:16,188 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:18:16,193 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 05:19:12,250 INFO ]: Timeout while computing interpolants [2018-06-22 05:19:12,451 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:19:12,451 WARN ]: Verification canceled [2018-06-22 05:19:12,455 WARN ]: Timeout [2018-06-22 05:19:12,455 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:19:12 BoogieIcfgContainer [2018-06-22 05:19:12,455 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:19:12,456 INFO ]: Toolchain (without parser) took 69667.21 ms. Allocated memory was 298.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 248.4 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:19:12,457 INFO ]: SmtParser took 0.14 ms. Allocated memory is still 298.8 MB. Free memory is still 264.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 05:19:12,457 INFO ]: ChcToBoogie took 133.64 ms. Allocated memory is still 298.8 MB. Free memory was 247.4 MB in the beginning and 245.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:19:12,459 INFO ]: Boogie Preprocessor took 44.81 ms. Allocated memory is still 298.8 MB. Free memory was 245.4 MB in the beginning and 244.3 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. [2018-06-22 05:19:12,460 INFO ]: RCFGBuilder took 370.85 ms. Allocated memory is still 298.8 MB. Free memory was 244.3 MB in the beginning and 231.3 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:19:12,460 INFO ]: TraceAbstraction took 69105.55 ms. Allocated memory was 298.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 231.3 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:19:12,466 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.14 ms. Allocated memory is still 298.8 MB. Free memory is still 264.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 133.64 ms. Allocated memory is still 298.8 MB. Free memory was 247.4 MB in the beginning and 245.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 44.81 ms. Allocated memory is still 298.8 MB. Free memory was 245.4 MB in the beginning and 244.3 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 370.85 ms. Allocated memory is still 298.8 MB. Free memory was 244.3 MB in the beginning and 231.3 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 69105.55 ms. Allocated memory was 298.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 231.3 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 13 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 24 quantified variables from 22 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 69.0s OverallTime, 5 OverallIterations, 5 TraceHistogramMax, 0.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 4 SDslu, 46 SDs, 0 SdLazy, 24 SolverSat, 12 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 50 GetRequests, 23 SyntacticMatches, 7 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 1.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=13occurred in iteration=4, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 10.3s InterpolantComputationTime, 63 NumberOfCodeBlocks, 63 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 56 ConstructedInterpolants, 0 QuantifiedInterpolants, 1713 SizeOfPredicates, 15 NumberOfNonLiveVariables, 557 ConjunctsInSsa, 76 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 0/28 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig20.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-19-12-478.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig20.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-19-12-478.csv Completed graceful shutdown