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_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/pc_sfifo_2.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 14:09:28,418 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 14:09:28,420 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 14:09:28,431 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 14:09:28,431 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 14:09:28,432 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 14:09:28,433 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 14:09:28,437 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 14:09:28,439 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 14:09:28,439 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 14:09:28,442 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 14:09:28,442 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 14:09:28,443 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 14:09:28,444 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 14:09:28,445 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 14:09:28,447 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 14:09:28,449 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 14:09:28,451 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 14:09:28,452 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 14:09:28,453 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 14:09:28,454 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 14:09:28,457 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 14:09:28,457 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 14:09:28,457 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 14:09:28,458 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 14:09:28,459 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 14:09:28,460 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 14:09:28,460 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 14:09:28,461 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 14:09:28,461 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 14:09:28,462 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 14:09:28,463 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 14:09:28,463 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 14:09:28,464 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 14:09:28,464 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 14:09:28,465 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 14:09:28,477 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 14:09:28,478 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 14:09:28,478 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 14:09:28,478 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 14:09:28,479 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 14:09:28,479 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 14:09:28,480 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 14:09:28,480 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 14:09:28,480 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 14:09:28,480 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 14:09:28,480 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 14:09:28,481 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 14:09:28,481 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 14:09:28,481 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 14:09:28,481 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 14:09:28,481 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 14:09:28,481 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 14:09:28,482 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 14:09:28,482 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 14:09:28,483 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 14:09:28,483 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 14:09:28,528 INFO ]: Repository-Root is: /tmp [2018-06-22 14:09:28,544 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 14:09:28,550 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 14:09:28,552 INFO ]: Initializing SmtParser... [2018-06-22 14:09:28,552 INFO ]: SmtParser initialized [2018-06-22 14:09:28,553 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/pc_sfifo_2.smt2 [2018-06-22 14:09:28,554 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 14:09:28,649 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/pc_sfifo_2.smt2 unknown [2018-06-22 14:09:29,122 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/pc_sfifo_2.smt2 [2018-06-22 14:09:29,130 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 14:09:29,150 INFO ]: Walking toolchain with 4 elements. [2018-06-22 14:09:29,150 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 14:09:29,150 INFO ]: Initializing ChcToBoogie... [2018-06-22 14:09:29,151 INFO ]: ChcToBoogie initialized [2018-06-22 14:09:29,153 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:09:29" (1/1) ... [2018-06-22 14:09:29,244 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29 Unit [2018-06-22 14:09:29,244 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 14:09:29,254 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 14:09:29,254 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 14:09:29,254 INFO ]: Boogie Preprocessor initialized [2018-06-22 14:09:29,285 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (1/1) ... [2018-06-22 14:09:29,285 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (1/1) ... [2018-06-22 14:09:29,299 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (1/1) ... [2018-06-22 14:09:29,299 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (1/1) ... [2018-06-22 14:09:29,309 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (1/1) ... [2018-06-22 14:09:29,310 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (1/1) ... [2018-06-22 14:09:29,313 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (1/1) ... [2018-06-22 14:09:29,317 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 14:09:29,318 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 14:09:29,318 INFO ]: Initializing RCFGBuilder... [2018-06-22 14:09:29,318 INFO ]: RCFGBuilder initialized [2018-06-22 14:09:29,319 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (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 14:09:29,355 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 14:09:29,355 INFO ]: Found specification of procedure False [2018-06-22 14:09:29,355 INFO ]: Found implementation of procedure False [2018-06-22 14:09:29,355 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 14:09:29,355 INFO ]: Found specification of procedure state [2018-06-22 14:09:29,355 INFO ]: Found implementation of procedure state [2018-06-22 14:09:29,356 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 14:09:29,356 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 14:09:29,356 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 14:09:29,675 INFO ]: Using library mode [2018-06-22 14:09:29,675 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:09:29 BoogieIcfgContainer [2018-06-22 14:09:29,675 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 14:09:29,679 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 14:09:29,679 INFO ]: Initializing TraceAbstraction... [2018-06-22 14:09:29,682 INFO ]: TraceAbstraction initialized [2018-06-22 14:09:29,683 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:09:29" (1/3) ... [2018-06-22 14:09:29,683 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@172b1f2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 02:09:29, skipping insertion in model container [2018-06-22 14:09:29,683 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:09:29" (2/3) ... [2018-06-22 14:09:29,684 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@172b1f2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 02:09:29, skipping insertion in model container [2018-06-22 14:09:29,684 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:09:29" (3/3) ... [2018-06-22 14:09:29,685 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 14:09:29,698 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 14:09:29,708 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 14:09:29,754 INFO ]: Using default assertion order modulation [2018-06-22 14:09:29,755 INFO ]: Interprodecural is true [2018-06-22 14:09:29,755 INFO ]: Hoare is false [2018-06-22 14:09:29,755 INFO ]: Compute interpolants for FPandBP [2018-06-22 14:09:29,755 INFO ]: Backedges is TWOTRACK [2018-06-22 14:09:29,755 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 14:09:29,755 INFO ]: Difference is false [2018-06-22 14:09:29,755 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 14:09:29,755 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 14:09:29,770 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 14:09:29,779 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 14:09:29,779 INFO ]: Found error trace [2018-06-22 14:09:29,780 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:09:29,780 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:09:29,785 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 14:09:29,787 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:09:29,787 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:09:29,824 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:29,824 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:09:29,824 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:29,859 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:29,980 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 14:09:29,982 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 14:09:29,983 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 14:09:29,984 INFO ]: Interpolant automaton has 4 states [2018-06-22 14:09:29,996 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 14:09:29,996 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:09:29,998 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 14:09:30,113 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:09:30,113 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 14:09:30,114 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 14:09:30,115 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 14:09:30,115 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:09:30,126 INFO ]: With dead ends: 13 [2018-06-22 14:09:30,126 INFO ]: Without dead ends: 13 [2018-06-22 14:09:30,128 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:09:30,144 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 14:09:30,162 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 14:09:30,163 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 14:09:30,164 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 14:09:30,165 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 14:09:30,165 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:09:30,165 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 14:09:30,165 INFO ]: Interpolant automaton has 4 states. [2018-06-22 14:09:30,165 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 14:09:30,166 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 14:09:30,166 INFO ]: Found error trace [2018-06-22 14:09:30,166 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:09:30,166 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:09:30,166 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 14:09:30,166 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:09:30,166 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:09:30,167 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:30,167 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:09:30,167 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:30,301 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:30,623 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 14:09:30,664 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:09:30,665 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:09:30,665 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 14:09:30,672 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:09:30,762 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:30,774 INFO ]: Computing forward predicates... [2018-06-22 14:09:32,746 WARN ]: Spent 1.51 s on a formula simplification. DAG size of input: 30 DAG size of output: 19 [2018-06-22 14:09:32,990 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:09:33,012 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:09:33,012 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-22 14:09:33,013 INFO ]: Interpolant automaton has 10 states [2018-06-22 14:09:33,013 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 14:09:33,014 INFO ]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2018-06-22 14:09:33,014 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 10 states. [2018-06-22 14:09:33,337 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 20 [2018-06-22 14:09:33,413 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:09:33,413 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 14:09:33,414 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 14:09:33,414 INFO ]: Start accepts. Automaton has 10 states. Word has length 13 [2018-06-22 14:09:33,414 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:09:33,414 INFO ]: With dead ends: 15 [2018-06-22 14:09:33,414 INFO ]: Without dead ends: 15 [2018-06-22 14:09:33,415 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2018-06-22 14:09:33,415 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 14:09:33,418 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 14:09:33,418 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 14:09:33,419 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 14:09:33,419 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 14:09:33,419 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:09:33,419 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 14:09:33,419 INFO ]: Interpolant automaton has 10 states. [2018-06-22 14:09:33,419 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 14:09:33,419 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 14:09:33,419 INFO ]: Found error trace [2018-06-22 14:09:33,419 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:09:33,420 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:09:33,420 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 14:09:33,420 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:09:33,420 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:09:33,421 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:33,421 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:09:33,421 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:33,498 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:33,750 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:09:33,750 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:09:33,750 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 14:09:33,765 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:09:33,845 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:09:33,845 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:33,852 INFO ]: Computing forward predicates... [2018-06-22 14:09:34,202 WARN ]: Spent 207.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 25 [2018-06-22 14:09:34,554 WARN ]: Spent 253.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 29 [2018-06-22 14:09:34,615 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:09:34,646 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:09:34,646 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 14:09:34,647 INFO ]: Interpolant automaton has 13 states [2018-06-22 14:09:34,647 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 14:09:34,647 INFO ]: CoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2018-06-22 14:09:34,647 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-22 14:09:35,217 WARN ]: Spent 542.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 43 [2018-06-22 14:09:35,450 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 27 [2018-06-22 14:09:35,930 WARN ]: Spent 457.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 39 [2018-06-22 14:09:35,963 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:09:35,963 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 14:09:35,966 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 14:09:35,966 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-22 14:09:35,966 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:09:35,966 INFO ]: With dead ends: 19 [2018-06-22 14:09:35,966 INFO ]: Without dead ends: 19 [2018-06-22 14:09:35,967 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=71, Invalid=201, Unknown=0, NotChecked=0, Total=272 [2018-06-22 14:09:35,967 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 14:09:35,970 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 14:09:35,970 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 14:09:35,970 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 14:09:35,971 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-22 14:09:35,971 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:09:35,971 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 14:09:35,971 INFO ]: Interpolant automaton has 13 states. [2018-06-22 14:09:35,971 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 14:09:35,971 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 14:09:35,971 INFO ]: Found error trace [2018-06-22 14:09:35,972 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:09:35,972 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:09:35,972 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 3 times [2018-06-22 14:09:35,972 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:09:35,972 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:09:35,972 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:35,972 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:09:35,972 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:36,084 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:36,441 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 14:09:36,442 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:09:36,442 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 14:09:36,452 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 14:09:36,561 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 14:09:36,561 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:36,573 INFO ]: Computing forward predicates... [2018-06-22 14:09:37,105 WARN ]: Spent 286.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 29 [2018-06-22 14:09:41,298 WARN ]: Spent 3.83 s on a formula simplification. DAG size of input: 42 DAG size of output: 34 [2018-06-22 14:09:42,399 WARN ]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 14:09:42,938 WARN ]: Spent 109.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 14:09:43,639 WARN ]: Spent 313.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 10 [2018-06-22 14:09:43,720 INFO ]: Checked inductivity of 36 backedges. 3 proven. 20 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-22 14:09:43,740 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:09:43,740 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 19 [2018-06-22 14:09:43,740 INFO ]: Interpolant automaton has 19 states [2018-06-22 14:09:43,741 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 14:09:43,741 INFO ]: CoverageRelationStatistics Valid=75, Invalid=267, Unknown=0, NotChecked=0, Total=342 [2018-06-22 14:09:43,741 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 19 states. [2018-06-22 14:09:44,333 WARN ]: Spent 525.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 46 [2018-06-22 14:09:44,653 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 29 [2018-06-22 14:09:45,067 WARN ]: Spent 391.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 44 [2018-06-22 14:09:45,097 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:09:45,097 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 14:09:45,097 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 14:09:45,097 INFO ]: Start accepts. Automaton has 19 states. Word has length 25 [2018-06-22 14:09:45,097 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:09:45,098 INFO ]: With dead ends: 21 [2018-06-22 14:09:45,098 INFO ]: Without dead ends: 21 [2018-06-22 14:09:45,098 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=140, Invalid=412, Unknown=0, NotChecked=0, Total=552 [2018-06-22 14:09:45,099 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 14:09:45,103 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 14:09:45,103 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 14:09:45,104 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 14:09:45,104 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 14:09:45,104 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:09:45,104 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 14:09:45,104 INFO ]: Interpolant automaton has 19 states. [2018-06-22 14:09:45,104 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 14:09:45,105 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 14:09:45,105 INFO ]: Found error trace [2018-06-22 14:09:45,105 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:09:45,105 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:09:45,105 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 4 times [2018-06-22 14:09:45,105 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:09:45,105 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:09:45,106 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:45,106 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:09:45,106 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:45,253 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:45,693 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 14:09:46,393 WARN ]: Spent 651.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 17 [2018-06-22 14:09:46,686 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 14:09:46,686 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:09:46,686 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 14:09:46,692 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 14:09:46,826 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 14:09:46,826 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:46,837 INFO ]: Computing forward predicates... [2018-06-22 14:09:48,746 WARN ]: Spent 1.49 s on a formula simplification. DAG size of input: 39 DAG size of output: 29 [2018-06-22 14:09:49,177 WARN ]: Spent 306.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 34 [2018-06-22 14:09:49,868 INFO ]: Checked inductivity of 55 backedges. 4 proven. 30 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:09:49,892 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:09:49,892 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 22 [2018-06-22 14:09:49,893 INFO ]: Interpolant automaton has 22 states [2018-06-22 14:09:49,893 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 14:09:49,893 INFO ]: CoverageRelationStatistics Valid=90, Invalid=372, Unknown=0, NotChecked=0, Total=462 [2018-06-22 14:09:49,893 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 22 states. [2018-06-22 14:09:50,393 WARN ]: Spent 469.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 60 [2018-06-22 14:09:50,613 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 31 [2018-06-22 14:09:50,907 WARN ]: Spent 261.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 46 [2018-06-22 14:09:51,269 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 44 [2018-06-22 14:09:51,712 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 58 [2018-06-22 14:09:51,755 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:09:51,755 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 14:09:51,758 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 14:09:51,758 INFO ]: Start accepts. Automaton has 22 states. Word has length 29 [2018-06-22 14:09:51,758 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:09:51,759 INFO ]: With dead ends: 23 [2018-06-22 14:09:51,759 INFO ]: Without dead ends: 23 [2018-06-22 14:09:51,759 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 98 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=178, Invalid=578, Unknown=0, NotChecked=0, Total=756 [2018-06-22 14:09:51,759 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 14:09:51,762 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 14:09:51,762 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 14:09:51,763 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 14:09:51,763 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 14:09:51,763 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:09:51,763 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 14:09:51,763 INFO ]: Interpolant automaton has 22 states. [2018-06-22 14:09:51,764 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 14:09:51,764 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 14:09:51,764 INFO ]: Found error trace [2018-06-22 14:09:51,764 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:09:51,765 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:09:51,765 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 5 times [2018-06-22 14:09:51,765 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:09:51,765 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:09:51,765 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:51,765 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:09:51,765 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:09:51,878 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:52,261 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 14:09:52,878 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:09:52,878 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:09:52,878 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:09:52,887 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 14:09:53,089 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-06-22 14:09:53,089 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:09:53,103 INFO ]: Computing forward predicates... [2018-06-22 14:09:53,569 WARN ]: Spent 324.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 29 [2018-06-22 14:09:53,949 WARN ]: Spent 261.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 34 [2018-06-22 14:09:54,549 WARN ]: Spent 460.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 40 [2018-06-22 14:09:55,769 WARN ]: Spent 767.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 46 [2018-06-22 14:09:56,661 WARN ]: Spent 332.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 43 [2018-06-22 14:09:57,389 INFO ]: Checked inductivity of 78 backedges. 11 proven. 45 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-22 14:09:57,421 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:09:57,421 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 28 [2018-06-22 14:09:57,422 INFO ]: Interpolant automaton has 28 states [2018-06-22 14:09:57,422 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 14:09:57,422 INFO ]: CoverageRelationStatistics Valid=125, Invalid=631, Unknown=0, NotChecked=0, Total=756 [2018-06-22 14:09:57,422 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 28 states. [2018-06-22 14:09:58,079 WARN ]: Spent 507.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 96 [2018-06-22 14:09:58,268 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 47 [2018-06-22 14:09:58,458 WARN ]: Spent 156.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 48 [2018-06-22 14:09:58,689 WARN ]: Spent 193.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 52 [2018-06-22 14:09:58,904 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 52 [2018-06-22 14:09:59,292 WARN ]: Spent 344.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 77 [2018-06-22 14:09:59,782 WARN ]: Spent 439.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 96 [2018-06-22 14:10:00,309 WARN ]: Spent 479.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 95 [2018-06-22 14:10:00,358 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:10:00,358 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 14:10:00,359 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 14:10:00,359 INFO ]: Start accepts. Automaton has 28 states. Word has length 33 [2018-06-22 14:10:00,359 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:10:00,360 INFO ]: With dead ends: 27 [2018-06-22 14:10:00,360 INFO ]: Without dead ends: 27 [2018-06-22 14:10:00,361 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=286, Invalid=974, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 14:10:00,361 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 14:10:00,365 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 14:10:00,365 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 14:10:00,366 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 14:10:00,366 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 33 [2018-06-22 14:10:00,366 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:10:00,366 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 14:10:00,366 INFO ]: Interpolant automaton has 28 states. [2018-06-22 14:10:00,366 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 14:10:00,367 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 14:10:00,367 INFO ]: Found error trace [2018-06-22 14:10:00,367 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:10:00,367 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:10:00,367 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 6 times [2018-06-22 14:10:00,368 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:10:00,368 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:10:00,368 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:10:00,368 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:10:00,368 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:10:00,598 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:10:01,150 WARN ]: Spent 122.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 14:10:01,533 WARN ]: Spent 335.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 16 [2018-06-22 14:10:01,821 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 52 [2018-06-22 14:10:02,042 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 69 [2018-06-22 14:10:02,394 WARN ]: Spent 337.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 59 [2018-06-22 14:10:02,567 WARN ]: Spent 156.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 41 [2018-06-22 14:10:03,127 WARN ]: Spent 236.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 34 [2018-06-22 14:10:03,297 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 14:10:03,297 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:10:03,297 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 14:10:03,307 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:10:03,613 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2018-06-22 14:10:03,613 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:10:03,630 INFO ]: Computing forward predicates... [2018-06-22 14:10:04,024 WARN ]: Spent 301.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 29 [2018-06-22 14:10:04,950 WARN ]: Spent 340.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 39 [2018-06-22 14:10:06,311 WARN ]: Spent 552.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 57 [2018-06-22 14:10:07,948 WARN ]: Spent 953.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 65 [2018-06-22 14:10:11,287 WARN ]: Spent 1.06 s on a formula simplification. DAG size of input: 100 DAG size of output: 69 [2018-06-22 14:10:12,292 WARN ]: Spent 460.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 59 [2018-06-22 14:10:13,331 INFO ]: Checked inductivity of 136 backedges. 19 proven. 78 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-22 14:10:13,352 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:10:13,352 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18] total 35 [2018-06-22 14:10:13,353 INFO ]: Interpolant automaton has 35 states [2018-06-22 14:10:13,353 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 14:10:13,353 INFO ]: CoverageRelationStatistics Valid=194, Invalid=996, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 14:10:13,354 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 35 states. [2018-06-22 14:10:14,747 WARN ]: Spent 1.29 s on a formula simplification. DAG size of input: 195 DAG size of output: 122 [2018-06-22 14:10:15,022 WARN ]: Spent 195.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 42 [2018-06-22 14:10:15,322 WARN ]: Spent 240.00 ms on a formula simplification. DAG size of input: 173 DAG size of output: 48 [2018-06-22 14:10:15,574 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 40 [2018-06-22 14:10:16,007 WARN ]: Spent 311.00 ms on a formula simplification. DAG size of input: 186 DAG size of output: 56 [2018-06-22 14:10:16,592 WARN ]: Spent 509.00 ms on a formula simplification. DAG size of input: 204 DAG size of output: 76 [2018-06-22 14:10:17,410 WARN ]: Spent 743.00 ms on a formula simplification. DAG size of input: 200 DAG size of output: 86 [2018-06-22 14:10:18,624 WARN ]: Spent 1.13 s on a formula simplification. DAG size of input: 199 DAG size of output: 100 [2018-06-22 14:10:20,252 WARN ]: Spent 1.54 s on a formula simplification. DAG size of input: 196 DAG size of output: 119 [2018-06-22 14:10:20,366 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:10:20,366 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 14:10:20,367 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 14:10:20,367 INFO ]: Start accepts. Automaton has 35 states. Word has length 41 [2018-06-22 14:10:20,367 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:10:20,368 INFO ]: With dead ends: 29 [2018-06-22 14:10:20,368 INFO ]: Without dead ends: 29 [2018-06-22 14:10:20,369 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 25 SyntacticMatches, 2 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 349 ImplicationChecksByTransitivity, 13.5s TimeCoverageRelationStatistics Valid=411, Invalid=1481, Unknown=0, NotChecked=0, Total=1892 [2018-06-22 14:10:20,369 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 14:10:20,372 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 14:10:20,372 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 14:10:20,373 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 14:10:20,373 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 14:10:20,373 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:10:20,373 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 14:10:20,374 INFO ]: Interpolant automaton has 35 states. [2018-06-22 14:10:20,374 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 14:10:20,375 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 14:10:20,375 INFO ]: Found error trace [2018-06-22 14:10:20,375 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:10:20,375 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:10:20,375 INFO ]: Analyzing trace with hash 1442343014, now seen corresponding path program 7 times [2018-06-22 14:10:20,375 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:10:20,375 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:10:20,376 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:10:20,376 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:10:20,376 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:10:20,562 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:10:21,031 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 14:10:21,352 WARN ]: Spent 264.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 14:10:21,593 WARN ]: Spent 161.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 25 [2018-06-22 14:10:21,884 WARN ]: Spent 282.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 65 [2018-06-22 14:10:22,218 WARN ]: Spent 319.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 68 [2018-06-22 14:10:22,694 WARN ]: Spent 457.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 77 [2018-06-22 14:10:23,190 WARN ]: Spent 468.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 70 [2018-06-22 14:10:23,345 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 47 [2018-06-22 14:10:23,645 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 27 [2018-06-22 14:10:23,806 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 27 [2018-06-22 14:10:23,983 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 38 [2018-06-22 14:10:24,140 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 33 [2018-06-22 14:10:24,243 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 14:10:24,244 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:10:24,244 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:10:24,250 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:10:24,490 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:10:24,507 INFO ]: Computing forward predicates... [2018-06-22 14:10:24,944 WARN ]: Spent 273.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 29 Received shutdown request... [2018-06-22 14:10:25,538 INFO ]: Timeout while computing interpolants [2018-06-22 14:10:25,738 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:10:25,738 WARN ]: Verification canceled [2018-06-22 14:10:25,744 WARN ]: Timeout [2018-06-22 14:10:25,744 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:10:25 BoogieIcfgContainer [2018-06-22 14:10:25,744 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 14:10:25,745 INFO ]: Toolchain (without parser) took 56614.14 ms. Allocated memory was 309.3 MB in the beginning and 1.2 GB in the end (delta: 909.1 MB). Free memory was 243.8 MB in the beginning and 915.7 MB in the end (delta: -671.9 MB). Peak memory consumption was 980.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:10:25,745 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:10:25,746 INFO ]: ChcToBoogie took 94.03 ms. Allocated memory is still 309.3 MB. Free memory was 241.8 MB in the beginning and 239.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:10:25,746 INFO ]: Boogie Preprocessor took 63.40 ms. Allocated memory is still 309.3 MB. Free memory was 239.8 MB in the beginning and 237.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:10:25,746 INFO ]: RCFGBuilder took 357.53 ms. Allocated memory is still 309.3 MB. Free memory was 237.8 MB in the beginning and 213.9 MB in the end (delta: 23.9 MB). Peak memory consumption was 23.9 MB. Max. memory is 3.6 GB. [2018-06-22 14:10:25,747 INFO ]: TraceAbstraction took 56064.78 ms. Allocated memory was 309.3 MB in the beginning and 1.2 GB in the end (delta: 909.1 MB). Free memory was 213.9 MB in the beginning and 915.7 MB in the end (delta: -701.8 MB). Peak memory consumption was 950.1 MB. Max. memory is 3.6 GB. [2018-06-22 14:10:25,754 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 94.03 ms. Allocated memory is still 309.3 MB. Free memory was 241.8 MB in the beginning and 239.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 63.40 ms. Allocated memory is still 309.3 MB. Free memory was 239.8 MB in the beginning and 237.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 357.53 ms. Allocated memory is still 309.3 MB. Free memory was 237.8 MB in the beginning and 213.9 MB in the end (delta: 23.9 MB). Peak memory consumption was 23.9 MB. Max. memory is 3.6 GB. * TraceAbstraction took 56064.78 ms. Allocated memory was 309.3 MB in the beginning and 1.2 GB in the end (delta: 909.1 MB). Free memory was 213.9 MB in the beginning and 915.7 MB in the end (delta: -701.8 MB). Peak memory consumption was 950.1 MB. 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 46 with TraceHistMax 10, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 232 quantified variables from 28 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 55.9s OverallTime, 8 OverallIterations, 10 TraceHistogramMax, 15.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 87 SDtfs, 265 SDslu, 525 SDs, 0 SdLazy, 470 SolverSat, 331 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 267 GetRequests, 112 SyntacticMatches, 3 SemanticMatches, 152 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 729 ImplicationChecksByTransitivity, 36.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=29occurred in iteration=7, 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, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.5s SatisfiabilityAnalysisTime, 33.4s InterpolantComputationTime, 325 NumberOfCodeBlocks, 325 NumberOfCodeBlocksAsserted, 32 NumberOfCheckSat, 312 ConstructedInterpolants, 0 QuantifiedInterpolants, 331396 SizeOfPredicates, 2421 NumberOfNonLiveVariables, 2810 ConjunctsInSsa, 226 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 222/636 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/pc_sfifo_2.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_14-10-25-765.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/pc_sfifo_2.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_14-10-25-765.csv Completed graceful shutdown